Idempotent endomorphisms of a graph (Q1587623)

Graphs considered are finite, undirected, without loops and multiple edges. A graph \(G\) is called \(S\)-unretractive if \(\text{sEnd}(G) = \text{Aut}(G)\), rigid if \(\text{End}(G) = \{\text{id}_G\}\) and asymmetric if \(\text{Aut}(G) = \{\text{id}_G\}\). A graph endormorphism is called strong if it preserves and reflects edges, \(\text{sEnd}(G)\) denotes the monoid of strong endomorphisms of \(G\). The graph congruence \(\tau\) identifies vertices which have the same neighbors. The main results are: (1) All idempotent endomorphisms of a graph \(G\) are strong iff \(\text{Aut}(G/\tau)= \text{End}(G/\tau)\). (2) All nonbijective strong endomorphisms of a graph \(G\) are idempotent iff either \(G\) is \(S\)-unretractive, or \(G/\tau\) is asymmetric and there is exactly one \(\tau\)-class of cardinality 2 while all the others have cardinality~1. Combination of the two results gives: Let \(G\) be a graph. Then \(\text{Idpt}(G) = (\text{sEnd}(G)\backslash \text{Aut}(G)) \cup \{\text{id}_G\}\) if and only if either \(G\) is unretractive, or \(G/\tau\) is rigid and there is exactly one \(\tau\)-class of cardinality 2 while all the others have cardinality 1. The author cites a result characterizing graphs with completely regular monoid \(\text{sEnd}(G)\) and proves by examples that the condition on idempotents in (1) implies complete regularity, not so the condition on idempotents in (2). Conversely, complete regularity does not imply either condition.