Idempotent endomorphisms of a graph (Q1587623)
From MaRDI portal
![]() | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Idempotent endomorphisms of a graph |
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Idempotent endomorphisms of a graph |
scientific article |
Statements
Idempotent endomorphisms of a graph (English)
0 references
23 July 2001
0 references
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.
0 references
unretractive
0 references
strong endomorphism
0 references
idempotent
0 references
completely regular
0 references
rigid
0 references
asymmetric
0 references