Inverse monoids of graphs (Q1568240): Difference between revisions

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.