Endomorphism spectra of graphs (Q686281)

Consider graphs \(G,H\) and a mapping \(f:V(G) \to V(H)\). Suppose that \(f\) is a homomorphism of \(G\) to \(H\), i.e., that any two vertices \(u,v\) in \(f(V(G))\), for which the sets \(f^{-1} (u)\) and \(f^{-1}(v)\) are joined in \(G\) by at least one edge, are adjacent in \(H\). If also conversely, for any two vertices \(u,v \in f(V(G))\) which are adjacent in \(H\), there is at least one edge of \(G\) between \(f^{-1}(u)\) and \(f^{-1}(v)\), then \(f\) is a halfstrong homomorphism; if in fact every vertex of \(f^{-1}(u)\) is adjacent in \(G\) to some vertex of \(f^{-1} (v)\) and conversely, then \(f\) is a locally strong homomorphism; if some vertex of \(f^{-1} (u)\) is adjacent in \(G\) to all vertices of \(f^{-1}(v)\) and conversely, then \(f\) is a quasi-strong homomorphism; finally, if every vertex of \(f^{-1}(u)\) is adjacent in \(G\) to every vertex of \(f^{-1}(v)\), then \(f\) is a strong homomorphism. The set of all homomorphisms \(G \to G\) (also termed endomorphisms of \(G)\) is denoted by \(\text{End} G\); similarly, \(\text{HEnd} G\), \(\text{LEnd} G\), \(\text{QEnd} G\), \(\text{SEnd} G\), \(\Aut G\) denote the sets of all halfstrong endomorphisms, all locally strong endomorphisms, all quasi-strong endomorphisms, all strong endomorphisms, and all automorphisms of \(G\). Clearly, \(\text{End} G \supseteq \text{HEnd} G \supseteq \text{LEnd} G \supseteq \text{QEnd } G \supseteq \text{SEnd} G \supseteq \Aut G\). There are 32 possibilities for the above inclusions to be strict or non-strict. The authors produce examples for almost all the possibilities (two are impossible and two are left open). Their examples have for the most part been generated by a computer program. With each example they provide additional information such as the endomorphism spectrum, i.e., the sequence of cardinalities \(| \text{End} G |\), \(| \text{HEnd} G |\), \(| \text{LEnd} G |\), \(| \text{QEnd} G |\), \(| \text{SEnd} G |\), \(| \Aut G |\). Interesting open problems are posed.