×

zbMATH — the first resource for mathematics

Endomorphisms of graphs. I: The monoid of strong endomorphisms. (English) Zbl 0683.05026
[Part II, cf. the review below.]
We use the fact that every graph is a generalized lexicographic product of an S-unretractive graph with sets, to show that the monoid of strong endomorphisms of any graph is isomorphic to a wreath product of a group with a certain small category. This implies information on algebraic properties of the monoid of strong endomorphisms. In particular, it is always a regular monoid.

MSC:
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20L05 Groupoids (i.e. small categories in which all morphisms are isomorphisms)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] H.Ahrends, Endomorphismenmonoide von Graphen und Distributivgesetze f?r Kompositionen von Graphen. Diplomarbeit, Oldenburg 1987.
[2] K. ?ulik, Zur Theorie der Graphen. Casopis Pest. Mat.83, 133-155 (1958).
[3] V. Fleischer, On the wreath product of monoids with categories. Proc. Acad. Sci. Estonian SSR35, 237-243 (1986) (in Russian). · Zbl 0615.20052
[4] V. Fleischer andU. Knauer, Endomorphism monoids of acts are wreath products of monoids with small categories. In: LNM1320, 84-96, Berlin-Heidelberg-New York 1988. · Zbl 0645.20045
[5] F.Harary, Graph theory. Reading, Mass. 1969. · Zbl 0182.57702
[6] Z. Hedrlin andA. Pultr, On rigid undirected graphs. Canad. J. Math.18, 1237-1242 (1966). · Zbl 0145.20603
[7] P. Hell, On some strongly rigid families of graphs and the full embeddings they induce. Algebra Universalis4, 108-126 (1974). · Zbl 0299.05109
[8] R. L. Hemminger, The group of anX-join of graphs. J. Combin. Theory5, 408-418 (1968). · Zbl 0184.49002
[9] J. M.Howie, An introduction to semigroup theory. New York-London 1976. · Zbl 0355.20056
[10] U. Knauer, Unretractive andS-unretractive joins and lexicographic products of graphs. J. Graph. Theory,11, 429-440 (1987). · Zbl 0659.05055
[11] U. Knauer andA. V. Mikhalev, Wreath products of orderd semigroups I, II. Semigroup Forum27, 331-350 (1983),31, 181-191 (1985). · Zbl 0524.06023
[12] M.Nieporte, Kategorielle Konstruktionen und Endomorphismenmonoide von Graphen. Diplomarbeit, Oldenburg 1987.
[13] U. Nummert, Endomorphism monoids of boolean products of graphs (Russian). TR? Toimetised764, 57-66 (1987.
[14] A. Pultr andZ. Hedrlin, Symmetric relations (undirected graphs) with given semigroups. Monatsh. Math.69, 318-322 (1965). · Zbl 0139.24803
[15] G. Sabidussi, The composition of graphs. Duke Math. J.26, 693-696 (1959). · Zbl 0095.37802
[16] G. Sabidussi, Graph derivates. Math. Z.76, 385-401 (1961). · Zbl 0109.16404
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.