Idempotent endomorphisms of a graph (Q1587623)

From MaRDI portal





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
    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
    0 references

    Identifiers