Structural aspects of semigroups based on digraphs

Source abstract

Given any digraph D without loops or multiple arcs, there is a natural construction of a semigroup 〈 D 〉 of transformations. To every arc ( a , b ) of D is associated the idempotent transformation ( a → b ) mapping a to b and fixing all vertices other than a . The semigroup 〈 D 〉 is generated by the idempotent transformations ( a → b ) for all arcs ( a , b ) of D . In this paper, we consider the question of when there is a transformation in 〈 D 〉 containing a large cycle, and, for fixed k ∈ ℕ , we give a linear time algorithm to verify if 〈 D 〉 contains a transformation with a cycle of length k . We also classify those digraphs D such that 〈 D 〉 has one of the following properties: inverse, completely regular, commutative, simple, 0-simple, a semilattice, a rectangular band, congruence-free, is 𝒦 -trivial or 𝒦 -universal where 𝒦 is any of Green’s ℋ -, ℒ -, ℛ -, or 𝒥 -relation, and when 〈 D 〉 has a left, right, or two-sided zero.