The Endomorphism Monoids of (n − 3)-regular Graphs of Order n

Boyko Gyurov, Ulrich Knauer, Sayan Panma, Nirutt Pipattanajinda


This paper is motivated by the result of W. Li, he presents an infinite family of graphs - complements of cycles - which possess a regular monoid. We show that these regular monoids are completely regular. Furthermore, we characterize the regular, orthodox and completely regular endomorphisms of the join of complements of cycles, i.e. (n−3)-regular graph of order n.


Complement of cycle; join; endomorphism monoid; complectly regular; orthodox

Full Text:



D. Amar, Irregularity strength of regular graphs of large degree, Discrete Math., N.114, 1993, pp. 9-17.

S. Fan, On end-regular graphs, Discrete Math., N.159, 1996, pp. 95-102.

F. Harary, Graph theory, Addison-Wesley, 1972.

H. Hou, Y. Luo, Graphs whose endomorphism monoids are regular, Discrete Math., N.308, 2008, pp. 3888-3896.

U. Knauer, Endomorphisms of graphs II. Various unretractive graphs, Arch. Math., N.55, 1990, pp. 193-203.

U. Knauer, Unretractive and S-unretractive joins and lexicographic products of graphs, J. Graph Theory, N.11, 1987(3), pp. 429-440.

W. Li, A regular endomorphism of a graph and its inverses, Mathematika, N.41, 1994, pp. 189-198.

W. Li, Graphs with regular monoids, Discrete Math., N.265, 2003, pp. 105-118.

W. Li, Green’s relations on the endomorphism monoid of a graph, Mathematica Slovaca, N.45, 1995(4), pp. 335-347.

M. Petrich, N. R. Reilly, Completely reguglar semigroups, Wiley Interscience, 1999.

B. M. Schin, B. Teclezghi, Endomorphisms of finite full transformation semigroups, in: The American Math. Socoety, Proceedings, N. 126, 1998(9), pp. 2579-2587.

A. Wilkeit, Graphs with regular endomorphism monoid, Arch. Math., N.66, 1996, pp. 344-352.