TY - JOUR

T1 - Nilpotent families of endomorphisms of (풫(V)+, ⋃)

AU - Fon-Der-Flaass, D.

AU - Kostochka, A.

AU - Nešetřil, J.

AU - Raspaud, A.

AU - Sopena, E.

N1 - Funding Information:
A directed graph G ¼ ðV , AÞ is k-nice if for every u, v 2 V (allowing t ¼ v), and for every orientation of the edges of an undirected path of length k, there exists a u − v walk of length k in G whose orientation coincides with that of the given path. A graph is nice if it is k-nice for some k. We generalize this notion using the notion of a nilpotent semigroup of endomorphisms of ðPðV Þþ, [Þ, and consider two basic problems: (1) find bounds for the nilpotency class of such semigroups in terms of their generators (in the language of graphs: provided that a graph G on n vertices is nice, find the smallest k such that G is k-nice); (2) find a way to demonstrate non-nilpotency of such semigroups (find as simple as possible characterization of non-nice graphs). © 2002 Elsevier Science (USA) 1This work was partially supported by the Grants 99-01-00581 and 97-01-01075 of the Russian Foundation for Fundamental Research. 2This work was partially supported by the Grant Intas-Open-97-1001 and the Dutch-Russian Grant NWO-047-008-006. 3Partially supported by the Project LN00A056 of the Czech Ministry of Education. 4This work was partially supported by the BARRANDE Programme 97-137. 5This research was partly supported by the NATO Collaborative Research Grant 97-1519.

PY - 2002

Y1 - 2002

N2 - A directed graph G = (V, A) is k-nice if for every u, v ε V (allowing t = v), and for every orientation of the edges of an undirected path of length k, there exists a u - v walk of length k in G whose orientation coincides with that of the given path. A graph is nice if it is k-nice for some k. We generalize this notion using the notion of a nilpotent semigroup of endomorphisms of (P(V)+, ∪), and consider two basic problems: (1) find bounds for the nilpotency class of such semigroups in terms of their generators (in the language of graphs: provided that a graph G on n vertices is nice, find the smallest k such that G is k-nice); (2) find a way to demonstrate non-nilpotency of such semigroups (find as simple as possible characterization of non-nice graphs).

AB - A directed graph G = (V, A) is k-nice if for every u, v ε V (allowing t = v), and for every orientation of the edges of an undirected path of length k, there exists a u - v walk of length k in G whose orientation coincides with that of the given path. A graph is nice if it is k-nice for some k. We generalize this notion using the notion of a nilpotent semigroup of endomorphisms of (P(V)+, ∪), and consider two basic problems: (1) find bounds for the nilpotency class of such semigroups in terms of their generators (in the language of graphs: provided that a graph G on n vertices is nice, find the smallest k such that G is k-nice); (2) find a way to demonstrate non-nilpotency of such semigroups (find as simple as possible characterization of non-nice graphs).

UR - http://www.scopus.com/inward/record.url?scp=0036747335&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036747335&partnerID=8YFLogxK

U2 - 10.1006/jctb.2002.2116

DO - 10.1006/jctb.2002.2116

M3 - Article

AN - SCOPUS:0036747335

VL - 86

SP - 100

EP - 108

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

SN - 0095-8956

IS - 1

ER -