Inverse monoids of graphs (Q1568240): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Semigroups of mappings on graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Endomorphisms of graphs. I: The monoid of strong endomorphisms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A regular endomorphism of a graph and its inverses / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An approach to construct an end-regular graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4887169 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4126563 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5572939 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Endomorphisms of graphs. II: Various unretractive graphs / rank | |||
Normal rank |
Revision as of 15:47, 29 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Inverse monoids of graphs |
scientific article |
Statements
Inverse monoids of graphs (English)
0 references
11 December 2000
0 references
A vertex map \(f\) of a graph \(G\) into itself which preserves edges is called a graph endomorphism. The author proves: (1) The endomorphism monoid \(\text{End}(G)\) of a graph \(G\) is an inverse monoid if and only if for every \(f\in \text{End}(G)\), there exists a unique idempotent \(g\in \text{End} (G)\) such that \(p_g = p_f\), and there exists a unique idempotent \(h\in \text{End}(G)\) such that \(I_h= I_f\). Here \(I_f\) denotes the endomorphic image of \(G\) under \(f\) with \(V(I_f) = f(V(G))\), and \(\{f(a), f(b)\}\in E(I_f)\) if and only if there exist \(c\in f^{-1} ( f(a))\) and \(d\in f^{-1} ( f(b))\) such that \(\{c,d\}\in E(G)\), where \(a,b,c,d \in V(G)\). Moreover, \(\rho_f\) denotes the equivalence relation on \(V(G)\) induced by \(f\), i.e., for \(a,b \in V(G)\), \((a,b)\in \rho_f\) if and only if \(f(a) = f(b)\). The author also proves: (2) If \(G\) is a bipartite graph, then \(\text{End}(G)\) is inverse if and only if \(G=K_2\), and (3) if \(G\) is a graph, then \(\text{End}(G)\) is inverse iff \(\text{End}(G + K_n)\) is inverse (\(n=1,2,\ldots\)). Some examples are given, too.
0 references
endomorphism
0 references
inverse monoid
0 references