Structural aspects of semigroups based on digraphs

Given any digraph D without loops or multiple arcs, there is a natural construction of a semigroup hDi 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 hDi 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 hDi containing a large cycle, and, for fixed k ∈ N, we give a linear time algorithm to verify if hDi contains a transformation with a cycle of length k. We also classify those digraphs D such that hDi has one of the following properties: inverse, completely regular, commutative, simple, 0-simple, a semilattice, a rectangular band, congruence-free, is K-trivial or K-universal where K is any of Green’s H-, L-, R-, or J -relation, and when hDi has a left, right, or two-sided zero.