Endomorphism spectra of graphs

✍ Scribed by Michael Böttcher; Ulrich Knauer

• Publisher: Elsevier Science
• Year: 1992
• Tongue: English
• Weight: 974 KB
• Volume: 109
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(92)90277-m

✦ Synopsis

In this paper we give an account of the different ways to define homomorphisms of graphs. This leads to six classes of endomorphisms for each gt aph. which as sets always form a chain by inclusion. The endomorphism spectrum is defined as a six-tuple containing the cardinalities of these six sets, and the endomorphism type is a number between 0 and 31 indicating which classes coincide. The well-known constructions by and by Hell (1979) of graphs with a prescribed endomorphism monoid always give graphs of endomorphism type 0 mod 2.

After the basic definitions in Section 1, we discuss some properties of the endomorphism classes in Section 2. Section 3 contains what is known about existence of certain endomorphism types, Secticn 4 gives a list of graphs with given endomorphism type, except for some cases where none have been found so far. Finally we formulate some problems connected with concepts presented here.