Idempotent endomorphisms of a graph
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.
This page was built for publication: Idempotent endomorphisms of a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1587623)
