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

D. Fon-Der-Flaass, A. Kostochka, J. Nešetřil, A. Raspaud, E. Sopena

Research output: Contribution to journalArticlepeer-review

Abstract

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).

Original languageEnglish (US)
Pages (from-to)100-108
Number of pages9
JournalJournal of Combinatorial Theory. Series B
Volume86
Issue number1
DOIs
StatePublished - 2002

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Nilpotent families of endomorphisms of (&#x1d4ab;(V)<sup>+</sup>, ⋃)'. Together they form a unique fingerprint.

Cite this