Endomorphism spectra of graphs
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.
- Endomorphism spectra of fan graphs.
- On irreducible endospectral graphs
- On endo-homology of complexes of graphs
- scientific article; zbMATH DE number 1159860
- The endomorphisms of Grassmann graphs
- Endomorphism spectra of wheel graphs.
- Endomorphisms of graph algebras
- Endomorphisms of functional graphs
- Endomorphism breaking in graphs
- Endomorphisms of graphs. II: Various unretractive graphs
- Endomorphisms of graphs. I: The monoid of strong endomorphisms
- Endomorphisms of graphs. II: Various unretractive graphs
- Graph derivatives
- scientific article; zbMATH DE number 3650785 (Why is no real title available?)
- scientific article; zbMATH DE number 3926946 (Why is no real title available?)
- scientific article; zbMATH DE number 3482390 (Why is no real title available?)
- scientific article; zbMATH DE number 3482391 (Why is no real title available?)
- scientific article; zbMATH DE number 1047891 (Why is no real title available?)
- On Rigid Undirected Graphs
- On some strongly rigid families of graphs and the full embeddings they induce
- Retract rigid Cartesian products of graphs
- Symmetric relations (undirected graphs) with given semigroups
- The monoid of strict endomorphisms of wreath products
- To the graph theory
- Unretractive and S-unretractive joins and lexicographic products of graphs
- Cayley graphs as classifiers for data mining: the influence of asymmetries
- Generalized symmetry of graphs - a survey
- An approach to construct an end-regular graph
- Postscript: ``Endomorphism spectra of graphs [Discrete Mathematics 109 (1992) 45--57]
- The endomorphism type of certain bipartite graphs and a characterization of projective planes
- Trees whose regular endomorphisms form a monoid
- Naturally ordered strong endomorphisms on graphs
- Correspondences of the semigroup of endomorphisms of an equivalence relation.
- Split graphs whose half-strong endomorphisms form a monoid
- Transformation semigroups preserving a binary relation.
- Endotypes of partial equivalence relations
- On regularity of semigroups of maps that preserve a binary relation
- On the endomorphism monoid of K(n,3)
- Unicyclic graphs with regular endomorphism monoids
- End-regular and End-orthodox generalized lexicographic products of bipartite graphs
- Semigroup theory of symmetry
- Generalized symmetry of graphs
- Semigroups of strong endomorphisms of infinite graphs and hypergraphs.
- End-regularity of zero-divisor graphs of group rings
- scientific article; zbMATH DE number 7450713 (Why is no real title available?)
- End-regular and End-orthodox lexicographic products of bipartite graphs
- scientific article; zbMATH DE number 7310257 (Why is no real title available?)
- THE JOIN OF SPLIT GRAPHS WHOSE QUASI-STRONG ENDOMORPHISMS FORM A MONOID
- Endomorphism spectra of wheel graphs.
- Endomorphism spectra of fan graphs.
- On endotype of bipartite graphs
- The join of split graphs whose regular endomorphisms form a monoid
- On unretractive graphs
- On unretractive graphs
- Endomorphism-regularity of split graphs
- The join of split graphs whose half-strong endomorphisms form a monoid
- On monoids of endomorphisms of a cycle graph
- On partial endomorphisms of a star graph
- Presentations for monoids of partial endomorphisms of a star graph
- End-regular flower graphs \(C_{r, s}\)
- Presentations for monoids of endomorphisms of a star graph
- The semigroup of weak endomorphisms of a partial equivalence relation
- The endomorphism monoid of \(\overline{P_n}\).
- On endomorphism-regularity of zero-divisor graphs
- On wreathed lexicographic products of graphs
This page was built for publication: Endomorphism spectra of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686281)
