The Endomorphism Monoids of (n − 3)-regular Graphs of Order n
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...
Збережено в:
| Дата: | 2016 |
|---|---|
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2016
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/155730 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | The Endomorphism Monoids of (n − 3)-regular Graphs of Order n / B. Gyurov, U. Knauer, S. Panma, N. Pipattanajinda // Algebra and Discrete Mathematics. — 2016. — Vol. 22, № 2. — С. 284-300. — Бібліогр.: 12 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-155730 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1557302019-06-18T01:26:46Z The Endomorphism Monoids of (n − 3)-regular Graphs of Order n Gyurov, B. Knauer, U. Panma, S. Pipattanajinda, N. 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. 2016 Article The Endomorphism Monoids of (n − 3)-regular Graphs of Order n / B. Gyurov, U. Knauer, S. Panma, N. Pipattanajinda // Algebra and Discrete Mathematics. — 2016. — Vol. 22, № 2. — С. 284-300. — Бібліогр.: 12 назв. — англ. 1726-3255 2010 MSC:05C25, 05C38. http://dspace.nbuv.gov.ua/handle/123456789/155730 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
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. |
| format |
Article |
| author |
Gyurov, B. Knauer, U. Panma, S. Pipattanajinda, N. |
| spellingShingle |
Gyurov, B. Knauer, U. Panma, S. Pipattanajinda, N. The Endomorphism Monoids of (n − 3)-regular Graphs of Order n Algebra and Discrete Mathematics |
| author_facet |
Gyurov, B. Knauer, U. Panma, S. Pipattanajinda, N. |
| author_sort |
Gyurov, B. |
| title |
The Endomorphism Monoids of (n − 3)-regular Graphs of Order n |
| title_short |
The Endomorphism Monoids of (n − 3)-regular Graphs of Order n |
| title_full |
The Endomorphism Monoids of (n − 3)-regular Graphs of Order n |
| title_fullStr |
The Endomorphism Monoids of (n − 3)-regular Graphs of Order n |
| title_full_unstemmed |
The Endomorphism Monoids of (n − 3)-regular Graphs of Order n |
| title_sort |
endomorphism monoids of (n − 3)-regular graphs of order n |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2016 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/155730 |
| citation_txt |
The Endomorphism Monoids of (n − 3)-regular Graphs of Order n / B. Gyurov, U. Knauer, S. Panma, N. Pipattanajinda // Algebra and Discrete Mathematics. — 2016. — Vol. 22, № 2. — С. 284-300. — Бібліогр.: 12 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT gyurovb theendomorphismmonoidsofn3regulargraphsofordern AT knaueru theendomorphismmonoidsofn3regulargraphsofordern AT panmas theendomorphismmonoidsofn3regulargraphsofordern AT pipattanajindan theendomorphismmonoidsofn3regulargraphsofordern AT gyurovb endomorphismmonoidsofn3regulargraphsofordern AT knaueru endomorphismmonoidsofn3regulargraphsofordern AT panmas endomorphismmonoidsofn3regulargraphsofordern AT pipattanajindan endomorphismmonoidsofn3regulargraphsofordern |
| first_indexed |
2025-07-14T07:58:13Z |
| last_indexed |
2025-07-14T07:58:13Z |
| _version_ |
1837608356611620864 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 22 (2016). Number 2, pp. 284–300
© Journal “Algebra and Discrete Mathematics”
The endomorphism monoids
of (n − 3)-regular graphs of order n
Nirutt Pipattanajinda, Ulrich Knauer,
Boyko Gyurov and Sayan Panma
Communicated by V. Mazorchuk
Abstract. This paper is motivated by the result of W. Li,
that 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 graphs of order n.
Introduction and preliminaries
Endomorphism monoids of graphs are generalizations of automor-
phism groups of graphs. In recent years much attention has been paid to
endomorphism monoids of graphs and many interesting results concern-
ing graphs and their endomorphism monoids have been obtained. The
techniques that are used in those studies connect semigroup theory to
graph theory and establish relationships between graphs and semigroups.
We review the regularity of endomorphism monoids of graphs. A
characterization of regular elements in End(G) using endomorphic image
and kernel was given by Li, in 1994, see [7]. In 1996, the connected
bipartite graphs whose endomorphism monoids are regular and orthodox
were explicitly found by Wilkeit [12] and Fan [2], respectively. In 2003,
see [8], Li showed that the endomorphism monoids of C2n+1 (n > 1) are
2010 MSC: 05C25, 05C38.
Key words and phrases: Complement of cycle; join; endomorphism monoid;
complectly regular; orthodox.
N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma 285
groups and the endomorphism monoids of C2n are regular, where Cn
denotes the complement of a cycle Cn.
Characterization of the join product of graphs whose endomorphism
monoids are regular or orthodox were studied extensively throughout the
years, with Knauer discovering in 1987, that the endomorphism monoid
of complete r-partite graph - the join of totally disconnected graphs
Kn1 + . . . + Knr , r ∈ Z
+, is regular, see [5]. In 2003, Li showed that if
the endomorphism monoid of the join of graphs is regular, then each
endomorphism of the graphs is regular, and for any graph G, the endo-
morphism monoid of G is regular if and only if the endomorphism monoid
of the join of G and a complete graph is also regular, see [8]. In 2008,
Hou and Luo characterized graphs with regular endomorphism monoids
and graphs with orthodox endomorphism monoids studying joins of two
bipartite graphs, see [4].
Consider finite simple graphs G with vertex set V (G) and edge set
E(G). The number of vertices of G is often called the order of G. The
degree of a vertex u in a graph G is the number of vertices adjacent to u
and is denoted by dG(u) or simply by d(u) if the graph G is clear from
the context. If d(u) = r for every vertex u of G, where 0 6 r 6 n−1, then
G is called a r-regular. The complement (graph) G of G is a graph such
that V (G) = V (G) and {u, v} ∈ (G) if and only if {u, v} /∈ E(G) for any
a, b ∈ V (G), a 6= b. A subgraph H of G is called an induced subgraph, if
for any u, v ∈ V (H), {u, v} ∈ E(G) implies {u, v} ∈ E(H). The induced
subgraph H with V (H) = S is also denoted by 〈S〉. A clique of graph G
is a maximal complete subgraph of G. The clique number of G, denoted
by ω(G), is the maximal order among the cliques of G. Let G and H be
two graphs. The join of G and H, denoted by G+H, is a graph such that
V (G + H) = V (G) ∪ V (H) and E(G + H) = E(G) ∪ E(H) ∪ {{u, v}|u ∈
V (G), v ∈ V (H)}. The graph with vertex set {1, . . . , n}, such that n > 3,
and edge set {{i, i + 1}|i = 1, . . . , n} ∪ {1, n} is called a cycle Cn.
Let G and H be graphs. A (graph) homomorphism from a graph G
to a graph H is a mapping f : V (G) → V (H) which preserves edges, i.e.
{u, v} ∈ E(G) implies {f(u), f(v)} ∈ E(H). By G → H we denote that
there exists a homomorphism from G to H. A homomorphism f is called
an (graph) isomorphism if f is bijective and f−1 is a homomorphism.
We call G isomorphic to H and denote by G ∼= H, if there exists an
isomorphism f from G onto H. A homomorphism from G into itself is
called an (graph) endomorphism of G. An endomorphism f is said to be
locally strong if {f(u), f(v)} ∈ E(G) implies that for every preimage x
of f(u) there exists a preimage y of f(v) such that {x, y} ∈ E(G) and
286 The endomorphism monoids of (n − 3)-regular graphs
analogously for every preimage of f(v). An isomorphism from G into itself
is called an automorphism. In this paper we use the following notations:
• End(G), the set of all endomorphisms of G,
• End′(G), the set of all non-injective endomorphisms of G,
• LEnd(G), the set of all locally strong endomorphisms of G, and
• Aut(G), the set of all automorphisms of G.
A factor graph If of G under f which is a subgraph of G is called
the endomorphic image of G under f . This means, V (If ) = f(V (G))
and {f(u), f(v)} ∈ E(If ) if and only if there exist u′ ∈ f−1f(u) and
v′ ∈ f−1f(v) such that {u′, v′} ∈ E(G), where f−1(t) denotes the set of
preimages of some vertex t of G under the mapping f. By ρf , we denote
the equivalence relation on V (G) induced by f , i. e. for any u, v ∈ V (G),
(u, v) ∈ ρf if and only if f(u) = f(v).
Let S be a semigroup (monoid respectively). An element a of S is
called an idempotent if a2 = a. An element a of S is called a regular
if a = aa′a for some a′ ∈ S, such a′ is called a pseudo inverse to a.
The semigroup S is called regular if every element of S is regular. A
regular element a of S is called completely regular if there exists a pseudo
inverse a′ to a such that aa′ = a′a. In this case we call a′ a commuting
pseudo inverse to a. The semigroup S is called completely regular if
every element of S is completely regular. A regular semigroup S is called
orthodox if the set of all idempotent elements of S (denoted by Idpt(S))
forms a semigroup under the operation of S. The Green’s relations H
on S are defined by aHb ⇔ S1a = S1b and aS1 = bS1. We denote the
equivalence class H of S containing element a by Ha.
Lemma 1 ([10]). Let S be a semigroup and e be an idempotent of S.
Then He is a subgroup of S.
Lemma 2 ([10]). A semigroup S is completely regular if and only if S is
a union of (disjoint) groups.
We recall, finally, that a left group and a right group are semigroups
of the form Ll × G and G × Rr where G is a group and Ll and Rr is a
left zero semigroup and a right zero semigroup of order r, respectively,
i.e., Ll is a semigroup with multiplication lilj = li for all li, lj ∈ Ll and
Rr is a semigroup with the multiplication rirj = rj for all ri, rj ∈ Rr.
Note that every left group and every right group is a union of groups.
A graph G is endo-regular (endo-orthodox, endo-completely-regular)
if the monoid of all endomorphisms on G is regular (orthodox, completely
regular respectively). Further, a graph G is unretractive if End(G) =
Aut(G).
N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma 287
The following results have been proved:
Lemma 3 ([9]). Let G be a graph. Suppose f, g ∈ End(G) are regular.
Then fHg if and only if ρf = ρg and If = Ig.
Lemma 4 ([7]). Let G be a graph and let f ∈ End(G). Then f is regular
if and only if there exist idempotents g, h ∈ End(G) such that ρg = ρf
and If = Ih.
Lemma 5 ([8]). Let G be a graph. Then G is endo-regular if and only if
G + Kn is endo-regular for any n > 1.
Lemma 6 ([4]). Let G1 and G2 be two graphs. Then G1 + G2 is endo-
orthodox if and only if
(1) G1 + G2 is endo-regular, and
(2) Both of G1 and G2 are endo-orthodox.
Lemma 7 ([6]). Let G1 and G2 be graphs. The join G1+G2 is unretractive
if and only if G1 and G2 are unretractive.
Lemma 8 ([3]). (1) Aut(Cn) ∼= Dn, where Dn denotes the dihedral
group of degree n.
(2) Aut(Cn) = Aut(Cn).
1. Endo-regularity of complements of cycles
Recall that the complement of cycle Cn with vertex set V (Cn) =
{1, 2, . . . , n} is a graph Cn with the same vertex set and E(Cn) =
{{i, j} | n − 2 > |i − j| > 2, ∀i, j ∈ {1, 2, . . . , n}}.
In [8] W. Li, characterized the monoid of End(Cn). There he showed
that the End(C2m+1) ∼= D2m+1 (m > 2) where Dn denotes the dihedral
group of degree n, i.e. C2m+1 is unretractive, and the endomorphism
monoid of C2m (m > 2) is regular.
Lemma 9 ([8]). (1) C2n+1 (n > 1) is unretractive.
(2) C2n (n > 1) is endo-regular.
Furthermore, he showed that
Lemma 10 ([8]). (1) The cliques of C2m or C2m+1 are isomorphic
to Km.
(2) There exist exactly two cliques in C2m namely 〈{1, 3, . . . , 2m − 1}〉
and 〈{2, 4, . . . , 2m}〉.
288 The endomorphism monoids of (n − 3)-regular graphs
A full transformation semigroup TX on a set X is the set XX of
all transformations (i.e., self-maps) X → X of X with composition of
transformations as multiplication. We can assume that X = {1, 2, . . . , n}
and write Tn instead of TX , see [11]. For C3, it is easy to see that,
Lemma 11. End(C3) = End(K3) ∼= T3.
Let f ∈ End′(C2m). Next, we use the congruence relation by the endo-
morphism f to show the algebraic structure of the monoid of End′(C2m).
Lemma 12. Let f ∈ End(C2m). If f is non-injective, then either f(C2m) =
{1, 3, . . . , 2m − 1} or f(C2m) = {2, 4, . . . , 2m}.
Proof. Clearly, for the graph C2m, there exist two unique complete sub-
graphs Km of C2m where V (Km) = {1, 3, . . . , 2m − 1} or V (Km) =
{2, 4, . . . , 2m}. Now {x, y} /∈ E(C2m) ⇔ y = x + 1 or y = x − 1. Let
f ∈ End′(C2m). Then f(x) = f(y) ⇔ y = x + 1 or y = x − 1. There-
fore, f({1, 3, . . . , 2m − 1}) = f({2, 4, . . . , 2m}) = {1, 3, . . . , 2m − 1} or
f({1, 3, . . . , 2m − 1}) = f({2, 4, . . . , 2m}) = {2, 4, . . . , 2m}.
Example 1. Let f : V (C6) → V (C6) be defined by f =
(1 2 3 4 5 6
1 1 3 3 5 5
)
∈
End′(C6). The defining congruence relation ̺f can be exemplified as Fig-
ure 1a. There is exactly one other congruence relation which is exemplified
by Figure 1b. By the homomorphism theorem each endomorphism is spec-
ified by one of these 2 congruence relations and the possible embedding
of the Km into C2m.
Figure 1. Congruence relations on C6 induced by f
Lemma 13. End(C2m) = LEnd(C2m).
Proof. Obvious from Example 1.
N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma 289
Lemma 14. Consider the graph C2m, and f ∈ End′(C2m). Let ̺f be
the congruence of the graph C2m when defining x̺f y ⇔ f(x) = f(y)
which here means y = x + 1 or y = x − 1. Denote by (C2m)̺f
the
factor graph. Then either V ((C2m)̺f
) = {{1, 2}, . . . , {2m − 1, 2m}} or
V ((C2m)̺f
) = {{2m, 1}, . . . , {2(m − 1), 2m − 1}}.
Lemma 15. Let f ∈ End′(C2m) and f̂ : V ((C2m)̺f
) → V (C2m) be
defined by f̂(x̺f
) = y if f(x) = y. Then either f̂(C2m) = {1, 3, . . . , 2m−1}
or f̂(C2m) = {2, 4, . . . , 2m}.
From Lemmas 14 and 15, we can define the following classes of non-
injective endomorphisms on C2m by ̺f and element f(1) ∈ V (C2m).
1) Sor
m , the class of all endomorphisms f of C2m where f̂(C2m) are the
odd integers and f(1) = f(2), i.e. {1, 2} ∈ ̺f ,
2) Ser
m , the class of all endomorphisms f of C2m where f̂(C2m) are the
even integers and f(1) = f(2), i.e. {1, 2} ∈ ̺f ,
3) Sol
m, the class of all endomorphisms f of C2m where f̂(C2m) are the
odd integers and f(2m) = f(1), i.e. {2m, 1} ∈ ̺f , and
4) Sel
m, the class of all endomorphisms f of C2m where f̂(C2m) are the
even integers and f(2m) = f(1), i.e. {2m, 1} ∈ ̺f .
Example 2. For the semigroup End′(C6), we choose the following nota-
tions
Sor
3 =
{
id = sor
31
=
(
1 2 3 4 5 6
1 1 3 3 5 5
)
, sor
32
=
(
1 2 3 4 5 6
5 5 3 3 1 1
)
,
sor
33
=
(
1 2 3 4 5 6
1 1 5 5 3 3
)
, sor
34
=
(
1 2 3 4 5 6
3 3 1 1 5 5
)
,
sor
35
=
(
1 2 3 4 5 6
3 3 5 5 1 1
)
, sor
36
=
(
1 2 3 4 5 6
5 5 1 1 3 3
)}
,
Ser
3 =
{
id = ser
31
=
(
1 2 3 4 5 6
2 2 4 4 6 6
)
, ser
32
=
(
1 2 3 4 5 6
6 6 4 4 2 2
)
,
ser
33
=
(
1 2 3 4 5 6
2 2 6 6 4 4
)
, ser
34
=
(
1 2 3 4 5 6
4 4 6 6 2 2
)
,
ser
35
=
(
1 2 3 4 5 6
6 6 2 2 4 4
)
, ser
36
=
(
1 2 3 4 5 6
6 6 4 4 2 2
)
}
,
290 The endomorphism monoids of (n − 3)-regular graphs
and
Sol
3 =
{
id = sol
31
=
(
1 2 3 4 5 6
1 3 3 5 5 1
)
, sol
32
=
(
1 2 3 4 5 6
5 3 3 1 1 5
)
,
sol
33
=
(
1 2 3 4 5 6
1 5 5 3 3 1
)
, sol
34
=
(
1 2 3 4 5 6
3 5 5 1 1 3
)
,
sol
35
=
(
1 2 3 4 5 6
5 1 1 3 3 5
)
, sol
36
=
(
1 2 3 4 5 6
5 3 3 1 1 5
)
}
,
Sel
3 =
{
id = sel
31
=
(
1 2 3 4 5 6
6 2 2 4 4 6
)
, sel
32
=
(
1 2 3 4 5 6
4 2 2 6 6 4
)
,
sel
33
=
(
1 2 3 4 5 6
6 4 4 2 2 6
)
, sel
34
=
(
1 2 3 4 5 6
2 4 4 6 6 2
)
,
sel
35
=
(
1 2 3 4 5 6
4 6 6 2 2 4
)
, sel
36
=
(
1 2 3 4 5 6
4 2 2 6 6 4
)
}
.
Proposition 1. The sets Sor
m , Ser
m , Sol
m and Sel
m form groups isomorphic
to Sm.
Theorem 1. (1) C2m is endo-completely-regular, and
(2) | End′(C2m)| = 4|Sm| = 4m!.
Proof. (1) Since End′(C2m) is a union of groups Sor
m , Ser
m , Sol
m and Sel
m,
End′(C2m) is completely regular by Lemma 2.
(2) Obvious, since the cardinality of each Sor
m , Ser
m , Sol
m and Sel
m is
m!.
Now we analyze the algebraic structure of End′(C2m).
Lemma 16. Let x ∈ {o, e}, y ∈ {r, l} and X ∈ {Sor
m , Ser
m , Sol
m, Sel
m}. Then
(1) XSxr
m ⊆ Sx′r
m and also XSxl
m ⊆ Sx′l
m for x′ ∈ {o, e},
(2) Soy
m X ⊆ Soy′
m and also Sey
m X ⊆ Sey′
m for y′ ∈ {r, l}.
Proof. If f(1) = f(2) is odd or even, then gf(1) = gf(2) is also odd or
even. Similarly, if f(1) = f(2m) is odd or even, then gf(1) = gf(2m) is
also odd or even.
Proposition 2. Let x, x′ ∈ {o, e} and y, y′ ∈ {r, l}. Then Sxy′
m Sx′y
m = Sxy
m .
From Proposition 2, we get the algebraic structure of End′(C2m), see
Table 1, and Theorem 2.
N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma 291
◦ sor
m1
· · · sor
mm!
ser
m1
· · · ser
mm!
sol
m1
· · · sol
mm!
sel
m1
· · · sel
mm!
sor
m1
... Sor
m Sor
m Sol
m Sol
m
sor
mm!
ser
m1
... Ser
m Ser
m Sel
m Sel
m
ser
mm!
sol
m1
... Sor
m Sor
m Sol
m Sol
m
sol
mm!
sel
m1
... Ser
m Ser
m Sel
m Sel
m
sel
mm!
Table 1. The form of the semigroup of End′(C2m)
Theorem 2. The following statements are true:
(1) The sets Sor
m ∪ Ser
m and Sol
m ∪ Sel
m form left groups isomorphic to
L2 × Sm.
(2) The sets Sor
m ∪ Sol
m and Ser
m ∪ Sel
m form right groups isomorphic to
Sm × R2.
2. Endo-regularity of (n − 3)-regular graphs of order n
In this section, we consider the endo-regularity of an (n − 3)-regular
graph of order n. Let
r
+
i=1
Cni
= Cn1 + . . . + Cnr . In [1], Amar shows that
if G is an (n − 3)-regular graph of order n > 7, then G is 2-regular and,
thus, is a disjoint union of cycles. We rewrite this as
Lemma 17. Let G be a graph of order n > 3. Then G is (n − 3)-regular
graph if and only if G =
r
+
i=1
Cni
where n = n1 + . . . + nr and r > 1. In
particular r > 1 implies n > 6.
Example 3. The 5 types of non-isomorphic 9-regular graphs of order 12,
are shown in Figure 2.
292 The endomorphism monoids of (n − 3)-regular graphs
Figure 2. The 9-regular graphs of order 12 which are joins of one or two
complements of cycles
Take G =
r
+
i=1
Cni
, the (n − 3)-regular graph of order n, where n =
n1 + . . . + nr and r > 2. Set V (Cni
) = {1i, . . . , ni}. It is clear from
Lemma 9(1), that Cni
is unretractive if and only if ni is odd and ni > 5.
Then by Lemma 7, an (n − 3)-regular graph G of order n is unretractive
if and only if G =
r
+
i=1
Cni
where ni is odd and ni > 5, for all i = 1, . . . , r.
Consider the retractive (n − 3)-regular graph of order n.
N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma 293
Lemma 18. Let G be an (n − 3)-regular graph of order n and f ∈
End′(G). If f(xi) = f(yi) for two different elements xi, yi ∈ V (Cni
), then
yi = (x − 1)i or yi = (x + 1)i.
Lemma 19. There exists a homomorphism Cm → Cm′ if and only if
m < m′.
Proof. Necessity. First, let m, m′ be integers of the same type, or m even
and m′ odd. Then there exist k and k′, k > k′ such that (i) m = 2k,
m′ = 2k′, (ii) m = 2k + 1, m′ = 2k′ + 1, or (iii) m = 2k, m′ = 2k′ + 1,
respectively. Thus the cliques of Cm and Cm′ are isomorphic to Kk and
Kk′ , respectively. Therefore, Cm 6→ Cm′ .
Suppose now that m = 2k+1, m′ = 2k′, and the cliques of Cm and Cm′
are isomorphic to Kk and Kk′ , respectively. For each k > k′, it is easy to
see that Cm 6→ Cm′ . Case k = k′. Now the subgraphs 〈{1, 3, . . . , m − 2}〉
and 〈{2, 4, . . . , m−1}〉 of Cm are isomorphic to Kk, the cliques of Cm′ are
only 〈{1, 3, . . . , m′ − 1}〉 and 〈{2, 4, . . . , m′}〉 are also isomorphic to Kk
and V (Cm′) = {1, 3, . . . , m′ −1}∪{2, 4, . . . , m′}. Let f ∈ Hom(Cm, Cm′).
Then f({1, 3, . . . , m − 2}) and f({2, 4, . . . , m − 1}) is {1, 3, . . . , m′ − 1}
or {2, 4, . . . , m′}.
1) If f({1, 3, . . . , m − 2}) = f({2, 4, . . . , m − 1}) = {1, 3, . . . , m′ − 1},
then f(1) = f(2), f(3) = f(4), . . . , f(m − 2) = f(m − 1) and
f(m) /∈ {1, 3, . . . , m′ − 1}. Let f(m) = 2x where 2x ∈ {2, 4, . . . , m′}.
Since {m, y} ∈ E(Cm) for all y ∈ {2, 3, . . . , m − 2}, we get f(y) 6∈
{2x − 1, 2x + 1}, which is a contradiction.
2) If f({1, 3, . . . , m − 2}) = {1, 3, . . . , m′ − 1} and f({2, 4, . . . , m −
1}) = {2, 4, . . . , m′}, assume that f(1) = 1, then f(2) = 2, f(3) =
3, . . . , f(m − 1) = m′. But {1, m − 1} ∈ E(Cm), which is a contra-
diction.
For the cases f({1, 3, . . . , m − 2}) = f({2, 4, . . . , m − 1}) = {2, 4, . . . , m′},
and f({1, 3, . . . , m − 2}) = {2, 4, . . . , m′} and f({2, 4, . . . , m − 1}) =
{1, 3, . . . , m′ − 1}, the proofs are similar to (1) and (2), respectively.
Sufficiency. Let m < m′. Then there exists a homomorphism f from
Cm which is an embedding Cm′ by f |
Cm
which is the identity map, where
f |
Cm
denotes the restriction of f to Cm.
Corollary 2.36. Let G be an (n−3)-regular graph of order n, f ∈ End(G),
and let G contain the induced subgraphs Cm and Cm′. If f(Cm) ⊆ Cm′,
then m 6 m′.
Lemma 20. Let G be an (n − 3)-regular graph of order n, f ∈ End(G)
and let G contain induced subgraph C2m+1. If f(C2m+1) = X, then 〈X〉 ∼=
C2m+1.
294 The endomorphism monoids of (n − 3)-regular graphs
Proof. Suppose that ω(G) = s. If 〈X〉 6∼= C2m+1, then ω(〈X〉) = m′ and
m < m′. Thus ω(G \ C2m+1) = s − m and ω(G \ X) = s − m′. But since
s − m > s − m′, it is impossible that f |
G\C2m+1
is a homomorphism from
G \ C2m+1 to G \ X.
Let G be an (n − 3)-regular graph of order n. Denote by Gx and GE
set of all induced subgraphs Cx and C2m of G, respectively. Note that
Gx = ∅, if G does not contain an induced subgraph Cx. From Lemma 20,
we get that
Proposition 3. Let G be an (n − 3)-regular graph of order n. Then
(1) | End(G)| = | End(GE)|×| End(G3)|×| End(G5)|×| End(G7)|× . . .,
if Gx 6= ∅, for all x = 3, 5, 7, . . .,
(2) End(G3) ∼= Sm1 × T3, where |G3| = m1, and
(3) for each odd integer x > 5, End(Gx) = Aut(Gx) ∼= Sm2 ×Dx, where
|Gx| = m2.
Let G = C(2m1)1
+ . . . + C(2mr)r
be an (n − 3)-regular graph of order
n. Set Oi = {1i, 3i, . . . , (2mi − 1)i} and Ei = {2i, 4i, . . . , (2mi)i}. Denote
SX1,X2,··· ,Xr = X1 ∪ X2 ∪ . . . ∪ Xr where Xi ∈ {Oi, Ei}, 1 6 i 6 r.
Lemma 21. Let G = C(2m1)1
+ . . . + C(2mr)r
be an (n − 3)-regular graph
of order n. There exist exactly 2r maximal complete subgraphs Km of G,
where n = 2m.
Proof. Since V (C(2mi)i
) = Oi ∪ Ei and 〈Oi〉, 〈Ei〉 are isomorphic to
Kmi
, for each Xi ∈ {Oi, Ei} and SX1,X2,··· ,Xr = X1 ∪ X2 ∪ . . . ∪ Xr,
〈S〉 is a complete subgraph Km, where m = m1 + . . . + mr. From
|{SX1,X2,··· ,Xr |SX1,X2,··· ,Xr = X1 ∪ X2 ∪ . . . ∪ Xr}| = 2r, we get that
there exist exactly 2r maximal complete subgraphs Km of G such that
n = 2m.
Corollary 2.37. Let G = C(2m1)1
+ . . . + C(2mr)r
and f ∈ End(G).
Then f(SO1,··· ,Or ) = X1 ∪ . . . ∪ Xr and f(SE1,··· ,Er ) = Y1 ∪ . . . ∪ Yr where
Xi, Yi ∈ {Oi, Ei}, 1 6 i 6 r.
Lemma 22. Let G = C(2m1)1
+ . . . + C(2mr)r
and f ∈ End(G). If
Oi, Ei ∈ f(G) for some 1 6 i 6 r, then f(C(2mj)j
) = C(2mi)i
and
mj = mi for some 1 6 j 6 r.
Proof. If f(C(2mj)j
) 6⊆ C(2mi)i
for all j ∈ {1, . . . , r}, then there exists
mk 6= ml, xk ∈ V (C(2mk)k
) and yl ∈ V (C(2ml)l
) such that f(xk) =
(2z + 1)i ∈ Oi and f(yl) = (2z)i ∈ Ei. But {xk, yl} ∈ E(G), which is a
N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma 295
contradiction. Thus f(C(2mj)j
) ⊆ C(2mi)i
for some j ∈ {1, . . . , r}. From
Corollary 2.36, we get mj 6 mi. Then there exists xi, (x+1)i ∈ V (C(2mi)i
)
such that xi = f(yj) ∈ f(C(2mj)j
) but (x + 1)i /∈ f(C(2mj)j
). Suppose
(x + 1)i = f(x′
k) ∈ f(C(2mk)k
). Now {yj , x′
k} ∈ E(G) is contradiction to
{xi, (x + 1)i} /∈ E(G). Therefore, mj = mi.
Lemma 23. Let G = C(2m1)1
+ . . . + C(2mr)r
and f ∈ End(G). If
f(xi) = f((x + 1)i) for some xi ∈ V (C2mi
), then
(1) f(1i) = f(2i), f(3i) = f(4i), . . . , f((2mi − 1)i) = f((2mi)i), if x is
odd, or
(2) f((2mi)i) = f(1i), f(2i) = f(3i), . . . , f((2mi − 2)i) = f((2mi − 1)i),
if x is even.
Proof. Now the cliques of G are isomorphic to Km, where m=m1+...+mr.
(1) Let x be odd integer and x 6= 1. Suppose that f(1i) 6= f(2i). If
{f(1i), f(2i)} /∈ E(G), then f(1i) = yj and f(2i) = (y + 1)j , for some
yj , (y + 1)j ∈ V (C(2mj)j
). But f(xi) = f((x + 1)i) is a contradiction to
Lemma 22.
Then either (1) {xi, 1i} ∈ E(G) and {xi, 2i} ∈ E(G), or (2) {(x +
1)i, 1i} ∈ E(G) and {(x + 1)i, 2i} ∈ E(G), or both. Thus the cliques of
〈{f(xi), f((x + 1)i), f(1i), f(2i)}〉 are isomorphic to K3. Now the cliques
of 〈{xi, (x+1)i, 1i, 2i}〉 are isomorphic to K2. Therefore, G\K2 → G\K3.
Consider ω(G \ K2) = m − 2 and ω(G \ K3) = m − 3, respectively.
But since m − 2 > m − 3, it is impossible that f |G\K2
is a homomorphism
from G \ K2 to G \ K3.
For the case x = 1 and the case x is even integer, the proof is similar
to case (1).
Example 4. Let again f : V (C6) → V (C6) be defined by f =
(1 2 3 4 5 6
1 1 3 3 5 5
)
∈
End′(C6). The congruence relation ̺f can be exemplified as in Figure 1a.
There is exactly one other congruence relation which is exemplified in
Figure 1b. By the homomorphism theorem each endomorphism in specified
by one of these 2 congruence relations and the possible embedding of the
Km into C2m.
Then let G ∼= C61 + C62 and f : V (G) → V (G) be defined by
f =
(
11 21 31 41 51 61 12 22 32 42 52 62
11 21 31 41 51 61 12 12 32 32 52 52
)
∈ End′(G).
The defining congruence relation ̺f can be exemplified as C61+ Fig-
ure 1a (see Figure 3a). From Lemma 22 and Lemma 23, and by the homo-
296 The endomorphism monoids of (n − 3)-regular graphs
morphism theorem each endomorphism in specified by one of these 8 con-
gruence relation and the possible embedding of each case into G, as follows
C61+ Figure 1b, Figure 1a+C62 , Figure 1b+C62 , Figure 1a+Figure 1a,
Figure 1a+Figure 1b (see Figure 3b), Figure 1b+Figure 1a and Fig-
ure 1b+Figure 1b.
Figure 3. C6 + K3 and K3 + K3
Lemma 24. Let G = C(2m1)1
+ . . . + C(2mr)r
and f : V (G) → V (G).
Then f ∈ End(G) if and only if f satisfies:
(1) If f(xi) = f(yi) for some two different elements xi, yi ∈ V (Cni
),
then yi = (x − 1)i or yi = (x + 1)i.
(2) f(SO1,··· ,Or ) = X1 ∪ . . . ∪ Xr and f(SE1,··· ,Er ) = Y1 ∪ . . . ∪ Yr where
Xi, Yi ∈ {Oi, Ei}, 1 6 i 6 r.
(3) If Oi, Ei ∈ f(G) for some 1 6 i 6 r, then f(C(2mj)j
) = C(2mi)i
and
mj = mi for some 1 6 j 6 r.
(4) If f(xi) = f((x + 1)i) for some xi ∈ V (C2mi
), then
(4.1) f(1i) = f(2i), f(3i) = f(4i), . . . , f((2mi − 1)i) = f((2mi)i), if
x is odd, or
(4.2) f((2mi)i) = f(1i), f(2i) = f(3i), . . . , f((2mi −2)i) = f((2mi −
1)i), if x is even.
Proof. Necessity. Obvious from Lemma 18, Corollary 2.37, Lemma 22
and Lemma 23.
Sufficiency. Obvious from Example 4.
Lemma 25. Let G = C(2m1)1
+ . . . + C(2mr)r
and f ∈ End(G). Then f
is an idempotent if and only if f |
C(2mi)i
is also idempotent in C(2mi)i
, for
all i = 1, . . . , r.
Example 5. For the monoid End(C61 + C62), we choose following
Idpt(End(C61 + C62)) =
N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma 297
{
id1 =
(
11 21 31 41 51 61 12 22 32 42 52 62
11 21 31 41 51 61 12 22 32 42 52 62
)
∈ D61 × D62 ,
id2 =
(
11 21 31 41 51 61 12 22 32 42 52 62
11 21 31 41 51 61 12 12 32 32 52 52
)
∈ D61 × Sor
32
,
id3 =
(
11 21 31 41 51 61 12 22 32 42 52 62
11 21 31 41 51 61 22 22 42 42 62 62
)
∈ D61 × Ser
32
,
id4 =
(
11 21 31 41 51 61 12 22 32 42 52 62
11 21 31 41 51 61 12 32 32 52 52 12
)
∈ D61 × Sol
32
,
id5 =
(
11 21 31 41 51 61 12 22 32 42 52 62
11 21 31 41 51 61 62 22 22 42 42 62
)
∈ D61 × Sel
32
,
id6 =
(
11 21 31 41 51 61 12 22 32 42 52 62
11 11 31 31 51 51 12 22 32 42 52 62
)
∈ Sor
31
× D62 ,
id7 =
(
11 21 31 41 51 61 12 22 32 42 52 62
21 21 41 41 61 61 12 22 32 42 52 62
)
∈ Ser
31
× D62 ,
id8 =
(
11 21 31 41 51 61 12 22 32 42 52 62
11 31 31 61 51 11 12 22 32 42 52 62
)
∈ Sol
31
× D62 ,
id9 =
(
11 21 31 41 51 61 12 22 32 42 52 62
61 21 21 41 41 61 12 22 32 42 52 62
)
∈ Sel
31
× D62 ,
id10 =
(
11 21 31 41 51 61 12 22 32 42 52 62
11 11 31 31 51 51 12 12 32 32 52 52
)
∈ Sor
31
× Sor
32
, . . . ,
id25 =
(
11 21 31 41 51 61 12 22 32 42 52 62
61 21 21 41 41 61 62 22 22 42 42 62
)
∈ Sel
31
× Sel
32
}
.
Let f ∈ End′(C61 + C62) be define by
f =
(
11 21 31 41 51 61 12 22 32 42 52 62
12 22 32 42 52 62 21 21 41 41 61 61
)
.
Then there exist unique idempotents id3 and id7 in End(C61 + C62) such
that ρf = ρid3 and If = Iid7 , respectively. So, f satisfies Lemma 4, i.e. f is
regular, but for each idempotent idk ∈ E(End(C61 + C62)), k = 1, . . . , 25,
has no both ρf = ρidk
and If = Iidk
. Thus f does not satisfy Lemma 3,
i.e. f /∈ Hidk
.
298 The endomorphism monoids of (n − 3)-regular graphs
Proposition 4. Let G = C(2m1)1
+. . .+C(2mr)r
. Then End(G) is regular.
Proof. Let f ∈ End(G). Then f satisfies (1)–(4) in Lemma 24.
Define e1 : V (G) → V (G) by e1(C(2mi)i
) = Xi ∪ Yi such that
1) if Xi = Yi = Oi, then e1(1i) = e1(2i) = 1i, e1(3i) = e1(4i) =
3i, . . . , e1((2mi − 1)i) = e1((2mi)i) = (2mi − 1)i,
2) if Xi = Yi = Ei, then e1(1i) = e1(2i) = 2i, e1(3i) = e1(4i) =
4i, . . . , e1((2mi − 1)i) = e1((2mi)i) = (2mi)i, and
3) if Xi 6= Yi, then e1|
C(2mi)i
is the identity map.
Thus e1 is idempotent in End(G) and If = Ie1 .
Define e2 : V (G) → V (G) by
1) e2|
C(2mj )j
is the identity map, if Oi, Ei ∈ f(G) for some 1 6 i 6 r,
then f(C(2mj)j
) = C(2mi)i
and mj = mi for some 1 6 j 6 r, and
2) e2(xi) = e2((x + 1)i) = xi, e2((x + 2)i) = e2((x + 3)i) = (x +
2)i, . . . , e2((x − 2)i) = e2((x − 1)i) = (x − 2)i (with addition modulo
2mi), if f(xi) = f((x + 1)i) for some xi ∈ V (C2mi
).
Thus e2 is idempotent in End(G) and ρf = ρe1 .
Thus, If = Ie1 and ρf = ρe2 . From Lemma 4, we get that f is
regular.
Lemma 26. Let G = C(2m1)1
+ . . . + C(2mr)r
. If mi = mj for some
i, j ∈ {1, . . . , r}, then there exist f ∈ End(G) such that f /∈ He for all
e ∈ E(End(G)).
Proof. Suppose m1 = m2 are even. Let f ∈ End(Cm1 + Cm2) be defined
by
f(xi) =
x2, i = 1;
x1, x is odd and i = 2;
(x − 1)1, x is even and i = 2.
Then If
∼= Cm2 + Km, where V (Km) = {11, 31, . . . , (m1 − 1)1}, and for
each x 6= y, (xi, yi) ∈ ρf ⇔ i = 2 and x2 = (y − 1)2. Let e be the
idempotent in End(Cm1 + Cm2) such that If = Ie and ρf = ρe. From
Lemma 25, we get that e|
Cm2
is the identity map. Since (x2, (x+1)2) ∈ ρe
for all x2, (x + 1)2 ∈ V (Cm2), this is a contradiction.
Lemma 27. Let G = C(2m1)1
+. . .+C(2mr)r
and f ∈ End(G). If mi 6= mj
for all i, j ∈ {1, . . . , r}, then f ∈ He for some e ∈ E(End(G)).
Proof. Let f ∈ End(G). From Proposition 4, f is regular.
Define e : V (G) → V (G) by e(C(2mi)i
) = Xi ∪ Yi such that
1) if Xi 6= Yi, then e|
C(2mi)i
is the identity map,
N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma 299
2) if Xi = Yi = Oi, then
(2.1) e(xi) = e((x + 1)i) = xi, e((x + 2)i) = e((x + 3)i) = (x +
2)i, . . . , e((x − 2)i) = e((x − 1)i) = (x − 2)i (with addition
modulo 2mi), if f(xi) = f((x + 1)i) for some odd integer
xi ∈ V (C2mi
), or
(2.2) e(xi) = e((x + 1)i) = (x + 1)i, e((x + 2)i) = e((x + 3)i) =
(x + 3)i, . . . , e((x − 2)i) = e((x − 1)i) = (x − 1)i (with addition
modulo 2mi), if f(xi) = f((x + 1)i) for some even integer
xi ∈ V (C2mi
), and
3) if Xi = Yi = Ei, then
(3.1) e(xi) = e((x + 1)i) = xi, e((x + 2)i) = e((x + 3)i) = (x +
2)i, . . . , e((x − 2)i) = e((x − 1)i) = (x − 2)i (with addition
modulo 2mi), if f(xi) = f((x + 1)i) for some even integer
xi ∈ V (C2mi
), or
(3.2) e(xi) = e((x + 1)i) = (x + 1)i, e((x + 2)i) = e((x + 3)i) =
(x + 3)i, . . . , e((x − 2)i) = e((x − 1)i) = (x − 1)i (with addition
modulo 2mi), if f(xi) = f((x + 1)i) for some odd integer
xi ∈ V (C2mi
).
Thus, If = Ie and ρf = ρe. From Lemma 3, we get f ∈ He.
Theorem 3. Let G be an (n − 3)-regular graph of order n. Then
(1) G is endo-regular, and
(2) G is endo-completely-regular if and only if |G3| = 0 and |G2m| = 1
for all induced subgraphs C2m of G.
Proof. (1) Since End(G3) is regular and for each odd integer x > 5,
End(Gx) = Aut(Gx) - form group - and from Proposition 3, End(G) is
regular, if End(GE) is also regular. Since End(GE) is always regular, from
Proposition 4, we get that G is endo-regular.
(2) Since End(G3) is not completely regular and for each odd integer
x > 5, End(Gx) = Aut(Gx) - form group - and from Proposition 3, End(G)
is completely regular if and only if |G3| = 0 and End(GE) is completely
regular. From Lemma 26 and Lemma 27, GE is endo-completely-regular
if and only if |G2m| = 1 for all induced subgraphs C2m of G.
Remark 2.38. A regular monoid S is called orthodox, if the set of all
idempotents from a submonoid of S. Since T3 is not orthodox, and from [8],
C2m also is not endo-orthodox, we get that the retractive (n − 3)-regular
graph of order n is not endo-orthodox.
References
[1] D. Amar, Irregularity strength of regular graphs of large degree, Discrete Math.,
N.114, 1993, pp. 9-17.
300 The endomorphism monoids of (n − 3)-regular graphs
[2] S. Fan, On end-regular graphs, Discrete Math., N.159, 1996, pp. 95-102.
[3] F. Harary, Graph theory, Addison-Wesley, 1972.
[4] H. Hou, Y. Luo, Graphs whose endomorphism monoids are regular, Discrete Math.,
N.308, 2008, pp. 3888-3896.
[5] U. Knauer, Endomorphisms of graphs II. Various unretractive graphs, Arch. Math.,
N.55, 1990, pp. 193-203.
[6] U. Knauer, Unretractive and S-unretractive joins and lexicographic products of
graphs, J. Graph Theory, N.11, 1987(3), pp. 429-440.
[7] W. Li, A regular endomorphism of a graph and its inverses, Mathematika, N.41,
1994, pp. 189-198.
[8] W. Li, Graphs with regular monoids, Discrete Math., N.265, 2003, pp. 105-118.
[9] W. Li, Green’s relations on the endomorphism monoid of a graph, Mathematica
Slovaca, N.45, 1995(4), pp. 335-347.
[10] M. Petrich, N. R. Reilly, Completely reguglar semigroups, Wiley Interscience, 1999.
[11] B. M. Schin, B. Teclezghi, Endomorphisms of finite full transformation semigroups,
in: The American Math. Socoety, Proceedings, N. 126, 1998(9), pp. 2579-2587.
[12] A. Wilkeit, Graphs with regular endomorphism monoid, Arch. Math., N.66, 1996,
pp. 344-352.
Contact information
N. Pipattanajinda Program of Mathematics, Faculty of Science and
Technology, Kamphaeng Phet Rajabhat Univer-
sity, Kamphaeng Phet 62000, THAILAND
E-Mail(s): nirutt.p@gmail.com
U. Knauer Institut für Mathematik, Carl von Ossietzky Uni-
versität, D-26111 Oldenburg, GERMANY
E-Mail(s): ulrich.knauer@uni-oldenburg.de
B. Gyurov School of Science and Technology, Georgia Gwin-
nett College, University System of Georgia,
Lawrenceville, GA 30043, USA
E-Mail(s): bgyurov@ggc.edu
S. Panma Department of Mathematics, Faculty of Sci-
ences, Chiang Mai University, Chiang Mai 50200,
THAILAND
E-Mail(s): panmayan@yahoo.com
Received by the editors: 16.03.2012
and in final form 03.03.2015.
|