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).
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics