Endomorphism-regularity of split graphs (Q5927687): Difference between revisions

The graphs considered are finite undirected graphs without loops and multiple edges. A graph \(G(V,E)\) is called a split graph if its vertex-set can be partitioned into disjoint (non-empty) sets \(S\) and \(K\), i.e., \(V = K\cup S\), such that \(S\) is a stable set and \(K\) is a complete graph, where stable means that the vertices of \(S\) are pairwise non-adjacent. The graph is called endo-regular if its endomorphism monoid is (von Neumann) regular. The authors prove: Let \(G(V,E)\) be a connected split graph with \(V= K\cup S\) and \(|K|= n\). Then \(G\) is endo-regular if and only if there exists \(r\in \{ 1,2,\ldots, n\}\) such that \(d(x) = r\) for any \(x\in S\); or there exists a vertex \(a\in S\) with \(d(a) = n\) and there exists \(r\in \{1,2,\ldots, n-1\}\) such that \(d(x) = r\) for any \(x\in S\backslash \{ a\}\) (if \(S\backslash \{ a\} \neq \emptyset\)). \parskip 0mm A non-connected split graph \(G\) is endo-regular if and only if \(G\) exactly consists of a complete graph and several isolated vertices. \parskip 0mm On the way it is proved that a regular element \(f\) of the endomorphism monoid of a graph \(G\) is always half strong, i.e., if \(\{f(a), f(b)\}\) is an edge, then there exist \(c\in f^{-1}\big(f(a)\big)\) and \(d\in f^{-1} \big(f(b)\big)\) such that \(\{ c,d\}\) is an edge, where \(a,b,c,d\in V\).