The endomorphisms monoids of graphs of order n with a minimum degree n − 3
We characterize the endomorphism monoids, End(G), of the generalized graphs G of order n with a minimum degree n − 3. Criteria for regularity, orthodoxy and complete regularity of those monoids based on the structure of G are given.
Збережено в:
| Дата: | 2014 |
|---|---|
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2014
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/153354 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | The endomorphisms monoids of graphs of order n with a minimum degree n − 3 / N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma // Algebra and Discrete Mathematics. — 2014. — Vol. 18, № 2. — С. 274–294. — Бібліогр.: 22 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-153354 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1533542019-06-15T01:26:56Z The endomorphisms monoids of graphs of order n with a minimum degree n − 3 Pipattanajinda, N. Knauer, U. Gyurov, B. Panma, S. We characterize the endomorphism monoids, End(G), of the generalized graphs G of order n with a minimum degree n − 3. Criteria for regularity, orthodoxy and complete regularity of those monoids based on the structure of G are given. 2014 Article The endomorphisms monoids of graphs of order n with a minimum degree n − 3 / N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma // Algebra and Discrete Mathematics. — 2014. — Vol. 18, № 2. — С. 274–294. — Бібліогр.: 22 назв. — англ. 1726-3255 2010 MSC:05C25, 05C38. http://dspace.nbuv.gov.ua/handle/123456789/153354 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
We characterize the endomorphism monoids, End(G), of the generalized graphs G of order n with a minimum degree n − 3. Criteria for regularity, orthodoxy and complete regularity of those monoids based on the structure of G are given. |
| format |
Article |
| author |
Pipattanajinda, N. Knauer, U. Gyurov, B. Panma, S. |
| spellingShingle |
Pipattanajinda, N. Knauer, U. Gyurov, B. Panma, S. The endomorphisms monoids of graphs of order n with a minimum degree n − 3 Algebra and Discrete Mathematics |
| author_facet |
Pipattanajinda, N. Knauer, U. Gyurov, B. Panma, S. |
| author_sort |
Pipattanajinda, N. |
| title |
The endomorphisms monoids of graphs of order n with a minimum degree n − 3 |
| title_short |
The endomorphisms monoids of graphs of order n with a minimum degree n − 3 |
| title_full |
The endomorphisms monoids of graphs of order n with a minimum degree n − 3 |
| title_fullStr |
The endomorphisms monoids of graphs of order n with a minimum degree n − 3 |
| title_full_unstemmed |
The endomorphisms monoids of graphs of order n with a minimum degree n − 3 |
| title_sort |
endomorphisms monoids of graphs of order n with a minimum degree n − 3 |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2014 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/153354 |
| citation_txt |
The endomorphisms monoids of graphs of order n with a minimum degree n − 3 / N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma // Algebra and Discrete Mathematics. — 2014. — Vol. 18, № 2. — С. 274–294. — Бібліогр.: 22 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT pipattanajindan theendomorphismsmonoidsofgraphsofordernwithaminimumdegreen3 AT knaueru theendomorphismsmonoidsofgraphsofordernwithaminimumdegreen3 AT gyurovb theendomorphismsmonoidsofgraphsofordernwithaminimumdegreen3 AT panmas theendomorphismsmonoidsofgraphsofordernwithaminimumdegreen3 AT pipattanajindan endomorphismsmonoidsofgraphsofordernwithaminimumdegreen3 AT knaueru endomorphismsmonoidsofgraphsofordernwithaminimumdegreen3 AT gyurovb endomorphismsmonoidsofgraphsofordernwithaminimumdegreen3 AT panmas endomorphismsmonoidsofgraphsofordernwithaminimumdegreen3 |
| first_indexed |
2025-07-14T04:34:48Z |
| last_indexed |
2025-07-14T04:34:48Z |
| _version_ |
1837595559117979648 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 18 (2014). Number 2, pp. 274–294
© Journal “Algebra and Discrete Mathematics”
The endomorphisms monoids of graphs
of order n with a minimum degree n − 3
Nirutt Pipattanajinda, Ulrich Knauer,
Boyko Gyurov and Sayan Panma
Communicated by V. Mazorchuk
Abstract. We characterize the endomorphism monoids,
End(G), of the generalized graphs G of order n with a minimum de-
gree n−3. Criteria for regularity, orthodoxy and complete regularity
of those monoids based on the structure of G are given.
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 start with a review of results obtained about 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, [9]. In 1996, the connected
bipartite graphs whose endomorphism monoids are regular and orthodox
This work was partially supported by the Faculty of Science and Technology, Kam-
phaeng Phet Rajabhat University, Kamphaeng Phet, Thailand and the School of Science
and Technology, Georgia Gwinnett College, Lawrenceville, GA.
2010 MSC: 05C25, 05C38.
Key words and phrases: Graph of order n which minimal degree n − 3, graph
endomorphism, regular, orthodox, completely regular.
N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma 275
were explicitly found by Wilkeit [22] and Fan [2], respectively. In 2003, [10],
Li showed that the endomorphism monoids of C2n+1 (n > 1) are groups,
where Cn denotes the complement of a cycle Cn. Further, Pipattanajinda
at al [17], proved that the endomorphism monoids of C2n are completely
regular. In 2008, Hou, Luo and Cheng proved that the endomorphism
monoids of P n are orthodox, see [5]. Furthermore, the cycle book graphs,
generalized wheel graphs, N -prism graphs and splits graphs whose endo-
morphisms monoids are regular, orthodox and completely regular were
studied in [3, 12–14,16,19–21].
In this paper we consider finite simple graphs G with vertex set
V (G) and edge set E(G), with the number of vertices of G called the
order of G. The graph with vertex set {1, . . . , n}, with n > 3, [n > 1] and
edge set { {i, i + 1} | i = 1, . . . , n} ∪ {1, n}, [{ {i, i + 1} | i = 1, . . . , n}] is
called a cycle Cn, [a path Pn].
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. The minimum degree of G is the minimum
degree among the vertices of G and is denoted by δ(G). Thus, if G is a
graph of order n and u is any vertex of G, then
0 6 δ(G) 6 d(u) 6 n − 1.
If d(u) = r for every vertex u of G, where 0 6 r 6 n − 1, then G is
called r-regular graph. 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 dented 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)}.
Further, let G, (Hx)x∈G be graphs with Hx = (Vx, Ex). The generalized
lexicographic product (G − join) of G with (Hx)x∈G is defined as
V (G[(Hx)x∈G]) :=
{
(x, yx) | x ∈ V (G), yx ∈ V (Hx)
}
,
E(G[(Hx)x∈G]) :=
{
{(x, yx), (x′, y′
x)} | (x, x′) ∈ E(G)
}
⋃
{
{(x, yx), (x, y′
x)} | x ∈ V (G), (yx, y′
x) ∈ E(Hx)
}
.
276 The endomorphism monoids of graphs of order n
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). A homomorphism f is called
a (graph) isomorphism if f is a bijective and f−1 is a homomorphism. We
call G isomorphic to H and write 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 strong if for
all u, v ∈ V (G), {u, v} ∈ E(G) if and only if {f(u), f(v)} ∈ E(G). An
endomorphism f is said to be path strong (resp. cycle strong) if for every
path (or cycle) f(v1), f(v2), . . . , f(vl) in f(G) there exists a path (or cycle)
u1, u2, . . . , ul in G, where ui ∈ f−1f(vi), for all i = 1, 2, . . . , l and f−1(t)
denotes the set of preimages of some vertex t of G under the mapping
f . 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,
• SEnd(G), the set of all strong endomorphisms of G, and
• Aut(G), the set of all automorphisms of G.
The factor graph If of G under f which is a subgraph of G is called
the endomorphic image of G under f . More precisely, If is a graph with
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). 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 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.
Lemma 1 ([18]). A semigroup S is completely regular if and only if S is
a union of (disjoint) groups.
N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma 277
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).
The following results are used widely in this work:
Lemma 2 ([15]). Let G be a graph and f ∈ End(G). If f is a regular,
then f is a path strong. Furthermore if f is a regular, then f is a cycle
strong.
Lemma 3 ([9]). Let G be a graph and let f ∈ End(G). Then f is a
regular if and only if there exist idempotents g, h ∈ End(G) such that
ρg = ρf and If = Ih.
Lemma 4 ([10]). Let G1 and G2 be graphs. If G1 + G2 is endo-regular,
then G1 and G2 are both endo-regular.
Lemma 5 ([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 6 ([7]). Let G1 and G2 be graphs. The join G1+G2 is unretractive
if and only if G1 and G2 are unretractive.
Lemma 7 ([10]). Let G be a graph and let f ∈ End(G + s). Then there
exists g ∈ End(G + s) such that g(s) = s with ρg = ρf and Ig = If .
Lemma 8 ([10]). Let G be a graph. Then G is endo-regular if and only
if G + Kn is endo-regular for any n > 1, where Kn is the complete graph
of n vertices.
Lemma 9 ([15]). For all positive integer n, the cycle C2n is not endo-
completely-regular.
Lemma 10 ([10]). C2n+1 is unretractive.
Lemma 11 ([17]). C2n is endo-completely-regular.
Lemma 12 ([5]). The only clique of order n + 1 of P 2n+1 is isomorphic
to Kn+1.
Lemma 13 ([5]). P n is endo-orthodox.
278 The endomorphism monoids of graphs of order n
Lemma 14 ([6]). Complete r-partite graphs Kn1 + . . . + Knr is endo-
regular,for n1, . . . , nr ∈ N, r ∈ N.
Lemma 15 ([21]). Let G be a graph. Suppose f ∈ End(G) and f is a
regular. Then the following two statements are equivalent:
(1) f is a completely regular,
(2) there exists idempotent g∈End(G) such that f(G)=g(G) and ρf =ρg.
Lemma 16 ([1]). 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.
Let G be an (n − 3)-regular graph of order n. We denote by Gx and
GE the sets of all induced subgraphs Cx and C2m of G, respectively. Note
that Gx = ∅, if G has no induced subgraphs Cx.
Lemma 17 ([17]). Let G be an (n − 3)-regular graph of order n.
(1) G is endo-regular.
(2) G is endo-completely-regular if and only if |G3| = 0 and |G2m| = 1
for all induced subgraph C2m of G.
(3) G is endo-orthodox and also unretractive if and only if |G3| = 0
and |G2m| = 0 for all induced subgraph C2m of G, i.e. G =
r
+
i=1
Cni
where ni > 5, ni is odd for all i = 1, . . . , r.
Observe that Cn and P n are graphs with d(u) > n − 3 for all u ∈
V (Cn), V (P n). From Lemmas 11 and 13, Cn is endo-completely-regular
and P n is endo-orthodox.
Next, we characterize the join of complements of paths and cycles -
graphs of order n with minimum degree is n − 3 that are endo-regular,
endo-orthodox, endo-completely-regular. In section 1 we cover the cases
δ(G) = n − 1 and δ(G) = n − 2 and in section 2 – the case δ(G) = n − 3.
1. Endo-regularity of graphs G of order n with δ(G) = n−2
Clearly, the case δ(G) = n − 1 corresponds to the complete graph
Kn, which is unretractive, so let us focus on graphs G of order n with
δ(G) = n − 2. Such graphs have the following structure:
Lemma 18. Let G be an (n − 2)-regular graph of order n. Then G is the
complete r-partite graph K2 + . . . + K2, where n = 2r.
N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma 279
Proof. Let G 6= K2+. . .+K2, where n = 2r. Then G 6= K2∪. . .∪K2. Thus
there exists u ∈ V (G) such that d
G
(u) > 1. Since n−1 = dG(u)+d
G
(u) >
dG(u) + 1, we get dG(u) < n − 2, a contradiction with the assumption
on G.
Next, it is easy to get that
Proposition 1. Let G be an (n − 2)-regular graph of order n. Then
(1) G = Kr[K2, . . . , K2], where n = 2r,
(2) End(G) = SEnd(G),
(3) |End(G)| = 4rr!.
The proposition above follows directly from the following result
from [8]:
Lemma 19 ([8]). (1) SEnd(G[(Hx)x∈G]) is regular.
(2) SEnd(G[(Hx)x∈G]) is orthodox if and only if |V (Hx)| 6 2 for
all x ∈ G.
From Proposition 1(1)–(2) and Lemma 19(1)–(2), it is easy to see also
that,
Corollary 1. A (n − 2)-regular graph of order n is endo-regular. In
particular, (n − 2)-regular graph of order n is endo-orthodox.
For completeness of the discussion let us show the condition for endo-
complete-regularity of the (n − 2)-regular graph of order n.
Proposition 2. Let G be an (n − 2)-regular graph of order n. Then G
is endo-completely-regular if and only if n = 2.
Proof. Necessity. From K2 + K2 = C4. If n > 2, then we can rewrite
G = C4 +K2 + . . .+K2, where K2 + . . .+K2 is a complete (n−2)-partite
graph. From Lemma 9, C4 is not endo-completely-regular. Therefore, G
is not endo-completely-regular.
Sufficiency. Straightforward.
Next, we show that if the endomorphism monoid of the join of graphs
is completely regular, then each endomorphism of the graphs is completely
regular.
Proposition 3. Let G and H be graphs. If G + H is endo-completely-
regular, then G and H are both endo-completely-regular.
280 The endomorphism monoids of graphs of order n
Proof. If G is not endo-completely-regular, then there exist f ∈ End(G)
such that f is not completely regular. Let g : V (G + H) → V (G + H)
be define by g|G = f and g|H is identity map. Then g ∈ End(G + H)
and easy to see that g is not completely regular. Therefore, G + H is not
endo-completely-regular.
Moreover, it is easy to show that for any graph G which is endo-
orthodox (endo-completely-regular), the graph G + Kn is endo-orthodox
(endo-completely-regular).
Proposition 4. Let G be a graph and n > 1. Then the following state-
ments are true.
(1) G is endo-orthodox if and only if G + Kn is endo-orthodox, and
(2) G is endo-completely-regular if and only if G+Kn is endo-completely-
regular.
Proof. (1) Follows directly from Lemma 8 and Lemma 5.
(2) Necessity. Since G + Kn = G + K1 + . . . + K1, we only need
to prove that G is endo-completely-regular if and only if G + s is end-
completely-regular, where s is a singleton, that is s = K1. Let G be
endo-completely-regular. Consider G + s and let f ∈ End(G + s). From
Lemma 7 there exists g ∈ End(G+s) such that g(s) = s with ρg = ρf and
g(G + s) = f(G + s). Then g(G) ⊆ V (G), implies g|G, the restriction of g
on G, is completely regular endomorphism of G. From Lemma 15, there
exists idempotent h ∈ End(G) such that h(G) = g|G(G) and ρh = ρg|G .
Thus h′ : V (G + s) → V (G + s) define by h′|G = h and h′(s) = s is
idempotent endomorphism of G+s, and h(G+s) = g(G+s) and ρh = ρg.
So, ρh = ρf and h(G+s) = f(G+s), so f is completely regular. Therefore,
G + s is endo-completely-regular.
Sufficiency. Obvious from Proposition 3.
Finally, let G be a graph of order n for which δ(G) = n − 2 and
d(u) = n − 1, for some u ∈ V (G). Thus, the graph G is the join of the
complete graph Kk and the complete r-partite graph K2 + . . .+K2, where
n = k + 2r. Using Lemma 1, Proposition 2 and Proposition 4, we get:
Proposition 5. Let G be a graph of order n which δ(G) = n − 2. Then
(1) G is endo-orthodox;
(2) G is endo-completely-regular if and only if
|{u ∈ V (G) | d(u) = n − 2}| = 2, i.e. G = Kk + K2 when n = k + 2.
N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma 281
2. Endo-regularity of graphs G of order n with δ(G) = n−3
In this section we consider graphs G of order n with δ(G) = n − 3
and d(u) > n − 3, for some u ∈ V (G). Observe that C2n+1 is unretractive
with ω(C2n+1) = n, a fact that we use in the next Lemma.
Lemma 20. Let G be a graph, n > 2 and f ∈ Hom(C2n+1, G). If f is
not an injective map, then ω(C2n+1) < ω(G).
Proof. Let f ∈ Hom(C2n+1, G) be a non-injective homomorphism. As-
sume that ω(C2n+1) > ω(G). Without loss of generality, suppose that
f(1) = f(2). Now 〈{1, 3, . . . , 2n − 1}〉 ∼= 〈{2, 4, . . . , 2n}〉 ∼= Kn.
From 〈{f(1) = f(2), f(3), f(4), . . . , f(2n−1), f(2n)}〉 6∼= Kn+r, for all r >
1 and {x, y} ∈ E(C2n+1) ⇔ y 6= x ± 1, implies that f(3) = f(4), f(5) =
f(6), . . . , f(2n−1) = f(2n). Thus 〈{f(1), f(3), f(5), . . . , f(2n−1), f(2n+
1)}〉 ∼= Kn+1, a contradiction. Therefore, ω(C2n+1) < ω(G).
Corollary 2. Let G be a graph, n > 2 and f ∈ End(G + C2n+1). If
f(C2n+1) = X ⊆ G is non-injective, then ω(C2n+1) < ω(〈X〉).
Lemma 21. For any integer n which n > 2 and the edge e ∈ E(C2n+1),
the only clique of order n + 1 of C2n+1 + {e} is isomorphic to Kn+1.
Proof. Since C2n+1 +{e} ∼= P 2n+1, by Lemma 12, the only clique of order
n + 1 of C2n+1 + {e} is isomorphic to Kn+1.
Lemma 22. Let G be a graph, n > 2 and f ∈ End′(G + C2n+1). If
f(C2n+1) = X, then 〈X〉 ∼= C2n+1.
Proof. Suppose that the clique of G is isomorphic to Ks. Let f(C2n+1) =
X 6= C2n+1. Assume that 〈X〉 6∼= C2n+1.
1) If f(C2n+1) ⊆ G, then by Corollary 2 and Lemma 21, the clique of
〈X〉 is isomorphic to Km and n < m.
2) If f(C2n+1) 6⊆ G, then there exists x ∈ V (C2n+1) such that f(x) ∈
V (C2n+1), but f(x + 1) ∈ V (G). Thus {f(x), f(x + 1)} ∈ E(G +
C2n+1). So the clique of 〈X〉 is isomorphic to Km and n < m.
From the above two observations, the cliques of G \ C2n+1 and G \ X are
isomorphic to Ks−n and Ks−m, respectively. But since s − n > s − m,
it is impossible that f |
G\C2n+1
is a homomorphism from G \ C2n+1 to
G \ X.
282 The endomorphism monoids of graphs of order n
Lemma 23. If G is a graph of order n with δ(G) = n − 3, then G is
a join of a complete graph, complements of cycles and complements of
paths.
Proof. If G is not as described, that is G 6∼= Kk + Ci1 + . . . + Cir +
P j1 + . . . + P js , where k + i1 + . . . + ir + j1 + . . . + js = n, then G 6∼=
Kk ∪ Ci1 ∪ . . . ∪ Cir ∪ Pj1 ∪ . . . ∪ Pjs . Thus there exists u ∈ V (G) such
that d
G
(u) > 3. Since dG(u) + d
G
(u) = n − 1, dG(u) 6 n − 4, which is a
contradiction.
In [10] (see Lemma 4 in this work), Li has shown that the regularity
of the endomorphism monoid of the join of graphs implies that the
endomorphism monoid of each of the graphs is regular. We use Lemma 22
and Lemma 23, to show that the converse of Lemma 4 is true in the case
of a join of a graph G of order n with δ(G) = n − 3, joined with the
complement of an odd cycle, C2m+1, m > 2.
Proposition 6. Let G be a graph of order n with δ(G) = n − 3, and let
m > 2. Then G + C2m+1 is endo-regular if and only if G is endo-regular.
Proof. Necessity. Directly from Lemma 4, since C2m+1, m > 2 is unre-
tractive.
Sufficiency. Let G be endo-regular and f ∈ End(G + C2m+1), where
m > 2. Using Lemma 23, suppose that G = G′ +Codd, where Codd denotes
the join of all complements of odd cycles which length is more than 3.
Then G+C2m+1 = G′+Codd+C2m+1, where Codd+C2m+1 is unretractive.
From Lemma 22, we have f(G + C2m+1) = f(G′) ∪ f(Codd + C2m+1),
when f(G′) ∩ f(Codd + C2m+1) = ∅. From Lemma 4, G′ is endo-regular.
Thus f = f |G′ ∪ f |
Codd+C2m+1
is regular. Therefore, G + C2m+1 is endo-
regular.
Similarly to Proposition 6, we get the next result.
Corollary 3. Let G be a graph of order n with δ(G) = n − 3, and let
m > 2. Then G + C2m+1 is endo-orthodox (endo-completely-regular) if
and only if G is endo-orthodox (endo-completely-regular).
Take any two graphs G1 and G2, where G1 is a subgraph of G2
(G1 ⊆ G2). Recall that G1 is an induced subgraph of G2, if for any
u, v ∈ V (G1), {u, v} ∈ E(G2) implies {u, v} ∈ E(G1). We write G1 < G2,
in this case.
Now, let G be a graph of order n with δ(G) = n − 3. From Lemma 8
and Proposition 6, G is endo-regular if and only if G + Kk and G + C2m+1
N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma 283
are endo-regular for any k > 1 and m > 2. Then we consider only the
graph G of order n with δ(G) = n − 3 such that Kk ≮ G and C2m+1 ≮ G,
where k > 1 and m > 2. So, G = C2i1 + . . . + C2ir + P j1 + . . . + P js ,
where j1, . . . , js > 1 and 2i1 + . . . + 2ir + j1 + . . . + js = n.
Lemma 24. If G contains one of following induced subgraphs:
(1) P 2n + P m (except K2,2),
(2) P m + C3 (except K2,3),
(3) P 2n + C2m,
then G is not endo-regular.
Proof. First, we show that each of the graphs P 2n + P m (except K2,2),
C3 + P m (except K3,2) and P 2n + C2m are not endo-regular. To do that,
let us recall (see Lemma 2), that every regular endomorphism is a path
strong endomorphism. Thus, it suffices to show that for for each of the
listed graphs there exist an endomorphism which is not a path strong.
(1) P 2n + P m (except K2,2) is not endo-regular.
There are two possible cases:
(1.1) Let P 2n + P m = P (2n)1
+ P 22 (2n > 4) and let f ∈ End(P (2n)1
+
P 22) be defined by
f =
(
11 21 31 41 . . . (2n − 1)1 (2n)1
12 22 31 41 . . . (2n − 1)1 (2n)1
)(
12 22
11 11
)
.
Then f−1(22) = {21}, f−1(31) = {31} and {22, 31} ∈ E(P (2n)1
+ P m2).
But {21, 31} /∈ E(P (2n)1
+ P m2), that is f is not a path strong.
(1.2) Let P 2n +P m = P (2n)1
+P m2 (m2 > 3) and let f ∈ End(P (2n)1
+
P m2) be defined by
f =
(
11 21 31 41 51 61 . . . (2n − 1)1 (2n)1
12 12 41 41 61 61 . . . (2n)1 (2n)1
)
(
12 22 32 42 52 62 . . . (m − 1)2 m2
11 21 32 42 52 62 . . . (m − 1)2 m2
)
.
Then f−1(21) = {22}, f−1(32) = {32} and {21, 32} ∈ E(P (2n)1
+ P m2).
But {22, 32} /∈ E(P (2n)1
+ P m2), that is f is not a path strong.
(2) P (2n)1
+ C32 (2n > 4) is not endo-regular.
284 The endomorphism monoids of graphs of order n
Consider the endomorphism f ∈ End(P (2n)1
+ C32) defined by
f =
(
11 21 31 41 . . . (2n − 1)1 (2n)1
12 22 31 41 . . . (2n − 1)1 (2n)1
)(
12 22 32
11 11 11
)
.
Similarly to case (1), f is not a path strong.
(3) P (2n)1
+ C(2m)2
is not endo-regular.
Consider the map f ∈ End(P (2n)1
+ C(2m)2
) defined by
f =
(
11 21 31 41 51 61 . . . (2n − 1)1 (2n)1
12 12 41 41 61 61 . . . (2n)1 (2n)1
)
(
12 22 32 42 52 62 . . . (2m − 1)2 (2m)2
11 21 32 32 52 52 . . . (2m − 1)2 (2m − 1)2
)
.
Clearly, f−1(11) = {12}, f−1(21) = {22}, so (21, 32, 52, . . . , (2m − 1)2, 11)
is a paths of length m + 1 in f(P (2n)1
+ C(2m)2
). Assume that f is a
path strong. Then there exists a path (22, x(3), x(5), . . . , x(2m−1), 12) in
P (2n)1
+ C(2m)2
, where x(y) ∈ f−1(y2).
(1) From {22, x(3)} ∈ E(P (2n)1
+ C(2m)2
) and f−1(32) = {32, 42} it
follows that x(3) = 42.
(2) From {42, x(5)} ∈ E(P (2n)1
+ C(2m)2
) and f−1(52) = {52, 62} it
follows that x(5) = 62.
...
(m-1) From {(2m − 2)2, x(2m−1)} ∈ E(P (2n)1
+ C(2m)2
) and f−1((2m −
1)2) = {(2m − 1)2, (2m)2} it follows that x(2m−1) = (2m)2.
(m) But {(2m)2, 12} /∈ E(P (2n)1
+ C(2m)2
). A contradiction with the
properties of path strong maps.
Thus f is not a path strong.
In [6] (see Lemma 14), Knauer has shown that a complete r-partite
graph Kn1 + . . . + Knr is endo-regular. We use Lemma 24 and Lemma 14,
to show conditions for the graph G, such that G + P 2 and G + C3 are
endo-regular.
Corollary 4. G + P 2 is endo-regular if and only if G = C31 + . . . + C3r +
P 21 + . . . + P 2k
, where r ∈ Z+ and k ∈ Z+ ∪ {0}.
N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma 285
Proof. Necessity. Let G 6= C31 + . . . + C3r + P 21 + . . . + P 2k
. Then either
P m < G for some m > 3, or C2m < G for some m > 2. Thus either
P m + P 2 < G + P 2 for some m > 3, or C2m + P 2 < G + P 2 for some
m > 2. Therefore, G + P 2 is not endo-regular, by Lemma 24.
Sufficiency. By assumption, G + P 2 is the complete (r + k + 1)-partite
graph C31 + . . .+C3r +P 21 + . . .+P 2k
+P 2. Then G+P 2 is endo-regular,
by Lemma 14.
Corollary 5. G + C3 is endo-regular if and only if G is either C31 +
. . . + C3r + P 21 + . . . + P 2k
or C31 + . . . + C3r + C2m1 + . . . + C2mk
, where
r ∈ Z+ and k ∈ Z+ ∪ {0}.
Proof. Necessity. If P m < G (m > 2), then P m + C3 < G + C3. Thus
G + C3 is not endo-regular, by Lemma 24. Let G contains both induce
subgraphs P 2 and C2m i.e. P 2 + C2m < G. Then P 2 + C2m < G + C3. It
is not endo-regular, by Lemma 24.
Sufficiency. If G is C31 + . . . + C3r + P 21 + . . . + P 2k
, or C31 + . . . +
C3r + C2m1 + . . . + C2mk
, then G + C3 is endo-regular, by Lemma 14 and
Theorem 17(1).
2.1. +P 2nk+1 is endo-regular
Let us denote by +P 2nk+1, the graph which consists of k joins of
complements of odd paths with length > 3, that is, +P 2nk+1 = P (2n1+1)1
+
P (2n2+1)2
+ . . . + P (2nk+1)k
, for some ni ∈ Z+, i = 1, . . . , k. Note that,
+P 2nk+1 = ∅, if k = 0.
Now we introduce series of set notations that we use in the proofs in
this section.
Let B(ni) = {1i, 3i, . . . , (2ni + 1)i} be the set of all odd vertices of
P (2ni+1)i
and let B
(ni)
0i,0i
= {2i, 4i, . . . , (2ni)i} be the set of all even vertices
of P (2ni+1)i
. It is not hard to see that V (P (2ni+1)i
) = B(ni)∪B
(ni)
0i,0i
, that the
induced subgraph 〈B(ni)〉 of P (2ni+1)i
is isomorphic to the complete graph
Kni+1 and that the induced subgraph 〈B
(ni)
0i,0i
〉 of P (2ni+1)i
is isomorphic
to the complete graph Kni
.
We construct a family of vertex sets, generally denoted by B
(ni)
ri,si , where
r, s ∈ {0, 1, . . . , n} in the following fashion:
Given the set B
(ni)
0i,0i
– the set of all even vertices of P (2ni+1)i
, let us
consider the elements of B
(ni)
0i,0i
ordered by the natural order. For 1 6 r 6 n
and 0 6 s 6 n, let the set B
(ni)
ri,si equal to the set B
(ni)
0i,0i
with the first
286 The endomorphism monoids of graphs of order n
r and the last s elements on B
(ni)
0i,0i
replaced by their odd predecessors.
That is, for x = 1, . . . , r we replace (2x)i ∈ B
(ni)
0i,0i
by (2x − 1)i, and for
y = s, . . . , n we replace (2y)i ∈ B
(ni)
0i,0i
by (2y + 1)i. Thus, we have:
B(ni)
ri,si
= {1i, 3i, 5i, . . . , (2r − 1)i, (2r + 2)i, (2r + 4)i, . . . , (2(s − 2))i,
(2(s − 1))i, (2s + 1)i, (2s + 3)i, (2s + 5)i, . . . , (2ni + 1)i}.
Finally, let X(nk) = B(n1) ∪ . . . ∪ B(nk) and X
(nk)
(r1,s1)···(rk,sk) = B
(n1)
(r1,s1) ∪
. . . ∪ B
(nk)
(rk,sk). Then V (+P 2nk+1) = X(nk) ∪ X
(nk)
(01,01)···(0k,0k), the induced
subgraph 〈X(nk)〉 of +P 2nk+1, is isomorphic to Kn1+1 + . . . + Knk+1
and the induced subgraph 〈X
(nk)
(r1,s1)···(rk,sk)〉 of +P 2ni+1 is isomorphic to
Kn1 + . . . + Knk
.
Corollary 6. There exists a homomorphism P 2m+1 → P 2n+1 if and only
if m 6 n.
Lemma 25. The following statements are true:
(1) There exists a unique maximal complete subgraph Kn1+1+. . .+Knk+1
of +P 2nk+1 of order
k
∑
i=1
ni+k, where V (Kn1+1+. . .+Knk+1)=X(nk).
(2) There exist exactly
k
∏
i=1
(3ni + 1) complete subgraphs Kn1 + . . . + Knk
of +P 2nk+1, where V (Kn1 + . . . + Knk
) = X
(nk)
(r1,s1)···(rk,sk) for some
0i 6 ri 6 ni and 0i 6 si 6 ni, i = 1, . . . , k such that ri + si 6 ni.
Now, for each graph +P 2nk+1 consider a map f ∈ End′(+P 2nk+1)
such that f(X(nk)) = X(nk), and f(X
(nk)
(01,01)···(0k,0k)) = X
(nk)
(r1,s1)···(rk,sk),
where ri, si ∈ {0i, 1i, . . . , nk}, ri + si 6 ni, for all i = 1, . . . , k.
Lemma 26. Let x, y ∈ V (+P 2nk+1). If f(x) = f(y), then x, y ∈
V (P (2ni+1)i
), for some i ∈ {1, . . . , k} and x = y − 1 or x = y + 1.
Next, we construct an additional family of vertex sets needed for the
discussion going further.
Let ri, si be positive integers where 0 6 ri 6 ni and 0 6 si 6 ni such
that ri + si 6 ni. We denote by B
(ni)
odd , B
(ni)
even and B
(ni)
both subsets of B
(ni)
ri,si
as follows:
B
(ni)
odd = {2x + 1 ∈ V (P (2ni+1)i
) | 2x + 1 ∈ B(ni) ∩ B(ni)
ri,si
},
B(ni)
even = {2x ∈ V (P (2ni+1)i
) | 2x ∈ B(ni) ∩ B(ni)
ri,si
}
B
(ni)
both = (B(ni) ∪ B(ni)
r,s ) \ B
(ni)
odd .
N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma 287
Note from the notation of B
(ni)
both, that its elements are B
(ni)
both = {x, x +
1, . . . , x + t − 1, x + t}, where x and x + t denotes the end vertices of
B
(ni)
both. In particular x and x + t are odd. We use these notations and the
observations that followed to prove the next result.
Lemma 27. If x, y ∈B
(ni)
both, for some i∈{1,. . . ,k}, then x, y ∈f(P (2nj+1)j
),
for some j ∈ {1, . . . , k}.
Proof. Assume that there exist two elements in B
(ni)
both such that one
element belongs to f(P (2nj+1)j
) and the other belongs to f(P (2ns+1)s
),
where j 6= s. Then, there exist x, x + 1 such that x ∈ f(P (2nt+1)t
),
and x + 1 ∈ f(P (2nt′ +1)t′
), where t 6= t′. But the elements of P (2nt+1)t
and P (2nt′ +1)t′
are adjacent, a contradiction to x and x + 1 being not
adjacent.
Proposition 7. For each P (2ni+1)i
, f(P (2ni+1)i
) contains only one B
(nj)
both ,
for some j ∈ {1, . . . , k}.
Proof. First, let P (2ni+1)i
< +P 2nk+1 such that f(P (2ni+1)i
) does not
contain B
(ni)
both, where i ∈ {1, . . . , k}. Then |f−1f(xi)| = 2, for all xi ∈
V (P (2ni+1)i
). This contradicts the fact that V (P (2ni+1)i
) contains only
odd elements.
Next, suppose that f(P (2ni+1)i
) contains B
(nj)
both and B
(nj′ )
both , for some
j, j′ ∈ {1, . . . , k} with j 6= j′. From Lemma 27, there exist P (2nt+1)t
such
that f(P (2nt+1)t
) does not contain any B
(nt′ )
both , a contradiction to the first
step.
Lemma 28. If x, x + t are the end vertices of B
(ni)
both, for some i ∈
{1, . . . , k}, then f(y + 1) = x + 1, . . . , f(y + t) = x + t, or the map-
ping is in the reversed order. In particular y and y + t are odd.
Proof. Let f(y+1) = x+1 and f(y+t) = x+t. Then, there exist x+s and
x + s + 1 such that f(y + s) = x + s, but f(y + s + 1) 6= x + s + 1. Suppose
that f(y + s′) = x + s + 1, where s′ 6= s + 1, then we get a contradiction
to x + s and x + s + 1 being not adjacent, but y + s and y + s′ are.
Observe also that, since x and x+t are odd, y and y+t are also odd.
From Lemma 28, we get directly
288 The endomorphism monoids of graphs of order n
Corollary 7. Let f(xi), f((x + t)i) be the end vertices of B
(nj)
both , for some
i, j ∈ {1, . . . , k}. Then
(1) f(1i) = f(2i), . . . , f((x − 2)i) = f((x − 1)i), and
(2) f((x + t + 1)i) = f((x + t + 2)i), . . . , f((2ni)i) = f((2ni + 1)i).
Next, recall that for every endomorphism f we have the induced
equivalence relation ̺f defined as u̺f v if and only if f(u) = f(v). Let us
provide an example for such relation.
Example 1. Let f : V (P 71 + P 52 + P 53) → V (P 71 + P 52 + P 53) be a
non-injective endomorphism, that is f ∈ End′(P 71 +P 52 +P 53) defined by
f =
(
11 21 31 41 51 61 71 12 22 32 42 52 13 23 33 43 53
12 12 23 23 32 11 11 31 41 51 43 43 52 52 71 71 53
)
.
The induced congruence relation ̺f can be visualized as in Figure 1.
[11] = {61, 71}
[31] = {12}
[41] = {22}
[51] = {32}
[71] = {33, 43}
[12] = {11, 21}
[32] = {51}
[52] = {13, 23}
[23] = {31, 41}
[43] = {42, 52}
[53] = {53}
+P 71
P 52
P 53
Figure 1. Congruence relation on P 71 + P 52 + P 53 induced by f
Lemma 29. Let f ∈ End(+P 2nk+1). Then
(1) If = Ig, for some idempotent g ∈ End(+P 2nk+1),
(2) ρf = ρh, for some idempotent h ∈ End(+P 2nk+1).
N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma 289
Proof. For each P (2nj+1)j
, let f(xi), f((x + t)i) be the end vertices of
B
(nj)
both , for some i, j ∈ {1, . . . , k}. Lemma 28 implies that f(xi) = yj ,
f((x + 1)i) = (y + 1)j , . . . , f((x + t)i) = (y + t)j [or in exactly reversed
order].
(1) Let us define g : V (+P 2nk+1) → V (+P 2nk+1) by
• g(yj) = yj , g((y + 1)j) = (y + 1)j , . . . , g((y + t)j) = (y + t)j ,
• g(1j)=g(2j)=1j , g(3j)=g(4j)=3j , . . . , g((y − 2)j) = g((y − 1)j) =
(y − 2)j ,
• g((y + t + 1)j) = g((y + t + 2)j) = (y + t + 2)j , g((y + t + 3)j) =
g((y+t+4)j) = (y+t+4)j , . . . , g((2nj)j) = g((2nj+1)j) = (2nj+1)j .
Further, let xi, yj ∈ V (+P 2nk+1) and {xi, yj} ∈ E(+P 2nk+1).
1) If i 6= j, then g(xi) ∈ V (P (2ni+1)i
) and g(yj) ∈ V (P (2nj+1)j
). Thus
{g(xi), g(yj)} ∈ E(+P 2nk+1).
2) If i = j, then g(xi), g(yi) ∈ V (P (2ni+1)i
) with y 6= x−1 and y 6= x+1,
or {xi, yi} = {1i, (2ni + 1)i}. From the definition of g we get that
{g(xi), g(yj)} ∈ E(+P 2nk+1).
Therefore, g ∈ End(+P 2nk+1) is an idempotent and If = Ig.
(2) Now, let us define h : V (+P 2nk+1) → V (+P 2nk+1) by
• h(xi) = xi, h((x + 1)i) = (x + 1)i, . . . , h((x + t)i) = (x + t)i,
• h(1i) = h(2i) = 1i, . . . , h((x − 2)i) = h((x − 1)i) = (x − 2)i,
• h((x + t + 1)i) = h((x + t + 2)i) = (x + t + 2)i, . . . , h((2ni)i) =
h((2ni + 1)i) = (2ni + 1)i.
In a similar fashion as in case (1) we have h ∈ End(+P 2nk+1) is an
idempotent and ρf = ρh.
Theorem 1. The graph +P 2nk+1 is endo-regular. In particular +P 2nk+1
is endo-orthodox.
Proof. The endo-regularity follows directly from Lemma 3 and Lemma 29.
Further, assuming the endo-regularity of +P 2nk+1, by Lemma 13 it
follows that each P 2ni+1 is endo-orthodox and thus by Lemma 5 if follows
that +P 2nk+1 is endo-orthodox.
290 The endomorphism monoids of graphs of order n
Further, let us denote by +C2ml
, the graph which consists of l joins
of complements of even cycles, that is, +C2ml
= C(2m1)1
+ C(2m2)2
+ . . . +
C(2ml)l
, for some mj ∈ Z+, j = 1, . . . , l. Let us denote by +P 2nk+1 +
+C2ml
, the join of the graphs +P 2nk+1 and +C2ml
. In the result above,
we established that +P 2nk+1 is endo-regular, and from Theorem 17(1),
+C2ml
is endo-regular. We show next that +P 2nk+1 + +C2ml
is not
endo-regular.
Proposition 8. The join graph +P 2nk+1 + +C2ml
is not endo-regular.
Proof. Since +P 2nk+1 + +C2ml
= (P n1 + Cm2) + [(+P 2nk+1 + +C2ml
) \
(P n1 + Cm2)], by Lemma 4, +P 2nk+1 + +C2ml
is not endo-regular, if
P n1 + Cm2 is not endo-regular. Thus, it suffices to show that P n1 + Cm2
is not endo-regular, with n > 3, n−odd and m > 4, m−even.
To achieve that, consider the map f ∈ End(P n1 + Cm2) defined as
f =
(
11 21 31 41 51 . . . (n − 1)1 n1
12 22 32 51 51 . . . n1 n1
)
(
12 22 32 42 52 62 . . . (m − 1)2 m2
11 11 31 31 52 52 . . . (m − 1)2 (m − 1)2
)
.
Suppose that f is regular. From Lemma 3, there exist an idempotent
g ∈ End(P n1 + Cm2) such that If = Ig. Then
1) g(12) = 12, g(22) = 22, g(32) = 32, and
2) g(52) = g(62) = 52, g(72) = g(82) = 72, . . . , f((m − 3)2) =
f((m − 2)2) = (m − 3)2, f((m − 1)2) = f(m2) = (m − 1)2.
Since 12, 22, 32, 52, 72, . . . , (m − 3)2, (m − 1)2 ∈ V (If ) and 42 /∈ V (If ), we
get 42 /∈V (Ig). Now, we have g(42) 6=g(x), where x∈{12, 22, 62, 72, . . . , m2},
since {42, x} ∈ E(Cm2), for all x. Thus g(42) = g(32) or g(42) = g(52). But
g(52) = g(62), g(42) 6= g(52). Then g(42) = g(32) = 32. This contradicts
to {22, 42} ∈ E(Cm2), but {g(22), g(42)} /∈ E(Cm2). Therefore, f is not
regular.
2.2. Endo-regularity of graphs G of order n with δ(G) = n − 3
In this subsection we compile the results and provide complete char-
acterization of the endomorphism monoid of graphs G of order n with a
minimum degree n − 3, based on the structure of G.
N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma 291
Everywhere further in the section G is a graph of order n with δ(G) =
n − 3, and we denote by G∗ the graph G∗ = G \ (Kt + (+C2ml+1)), where
Kt is the maximal complete subgraph of G and +C2ml+1 is the maximal
induced subgraph of the joins of complements of odd cycles which length
is more than 3. It is easy to see that G is unretractive if and only if V (G∗)
is empty.
First, we prove the following result.
Theorem 2. G is endo-regular if and only if G∗ is one of following
graphs:
(1) a complement of path,
(2) an (n − 2)-regular graph of order n,
(3) an (n − 3)-regular graph of order n,
(4) the join of complements of odd paths.
Proof. Necessity. Suppose that G∗ is not one of the graphs (1) to (4).
Then G contains one of following induced subgraphs:
1) P 2n + P m (except K2,2),
2) P n + C3 (except K2,3),
3) P n + C2m.
Therefore, G is not endo-regular, from Lemma 24 and Proposition 8.
Sufficiency. Obvious from Lemma 13, Corollary 1, Theorem 17(1) and
Theorem 1.
Next, we provide the results for endo-orthodoxy and endo-complete-
regularity of G.
Theorem 3. G is endo-orthodox if and only if G∗ is one of following
graphs:
(1) a complement of path,
(2) an (n − 2)-regular graph of order n,
(3) the join of complements of odd paths.
Proof. Necessity. Let G∗ be an (n − 3)-regular graph of order n. From
Lemma 17(2), G∗ is not endo-orthodox.
Sufficiency. Obvious from Lemma 13, Corollary 1 and Theorem 1.
292 The endomorphism monoids of graphs of order n
Theorem 4. If n > 4, then End(P n) is not completely regular.
Proof. For each n > 4, let
f =
(
1 2 3 . . . n − 3 n − 2 n − 1 n
3 4 5 . . . n − 1 n 1 1
)
∈ End(P n).
Since End(P n) is regular, let g be a pseudo inverse to f . Then exactly
g(3) = 1, g(4) = 2, . . . , g(n) = n − 2. Since {1, n}, {2, n} ∈ E(P n), we
have g(1) = g(2) = n. Thus gf(2) = g(4) = 2 and fg(2) = f(n) = 1.
Therefore, gf 6= fg, g is not a commuting pseudo inverse to f .
Lemma 30. P n is endo-completely-regular if and only if n 6 3.
Proof. Straightforward.
Lemma 31. Let +P 3k
be the k-joins of P 3.Then +P 3k
is endo-completely-
regular.
Proof. Let f ∈ End(+P 3k
). Then f |
X(3k) is injective from X(3k) - the
set of all odd vertices of +P 3k
- onto itself. Consider 2i ∈ V (P 3i
). If
f(2i) = 2j for some 2j ∈ V (P 3j
), then it is not hard to get that either
f |
P 3i
=
(1i2i3i
1j2j3j
)
or f |
P 3i
=
(1i2i3i
3j2j1j
)
. If f(2i) 6= 2j for all 2j ∈ V (+P 3k
),
then f(2i) = f(1i) or f(2i) = f(3i).
Let F2 be the set of all 2i ∈ V (+P 3k
) such that f(2i) = 2j for some
2j ∈ V (+P 3k
). Define g : V (+P 3k
) → V (+P 3k
) by
1) g|
X(3k)∪F2
= f−1|
X(3k)∪F2
,
2) g(2i) = g(1i) or g(2i) = g(3i), if f(2i) = f(1i) or f(2i) = f(3i), resp.
for each 2i /∈ F2.
It is clear that g ∈ End(+P 3k
), fgf(x) = f(x) and fg(x) = gf(x) =
x, for all x ∈ X(3k) ∪ F2.
Let 2i ∈ V (+P 3k
) such that f(2i) = f(1i). (The case f(2i) = f(3i) can
be proven similarly.) Then g(2i) = g(1i). Therefore, fgf(2i) = fgf(1i) =
f(1i) = f(2i) and fg(2i) = fg(1i) = gf(1i) = gf(2i).
Theorem 5. G is endo-completely-regular if and only if G∗ is one of
following graphs:
(1) a complement of the path of length 2,
(2) the join of complements of paths of length 3,
N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma 293
(3) an (n − 3)-regular graph of order n, where |G∗
3| = 0 and |G∗
2m| = 1
for all induced subgraphs C2m of G∗.
Proof. First, if G∗ is a (n−3)-regular graph of order n, by Theorem 17(3),
we get that G∗ is endo-completely-regular if and only if |G∗
3| = 0 and
|G∗
2m| = 1 for all induced subgraphs C2m of G∗.
Now suppose that G∗ is not a (n − 3)-regular graph of order n.
Necessity. Let G∗ be a graph P 2n or P 2n+1, where n > 1, by Lemma 30,
G∗ is not endo-completely-regular.
Sufficiency. Follows directly from Proposition 2 and Lemma 31.
References
[1] D. Amar, Irregularity strength of regular graphs of large degree, Discrete Math.,
N.114, 1993, pp. 9-17.
[2] S. Fan, On end-regular graphs, Discrete Math., N.159, 1996, pp. 95-102.
[3] S. Fan, Retractions of split graphs and End-orthodox split graphs, Discrete Math.,
N.257, 2002, pp. 161-164.
[4] H. Hou, Y. Luo, Graphs whose endomorphism monoids are regular, Discrete Math.,
N.308, 2008, pp. 3888-3896.
[5] H. Hou, Y. Luo, Z. Cheng, The endomorphism monoid of P n, European J. Com-
binatorics, N.29, 2008, pp. 1173-1185.
[6] U. Knauer, Endomorphisms of graphs II. Various unretractive graphs, Arch. Math.,
N.55, 1990, pp. 193-203.
[7] U. Knauer, Unretractive and S-unretractive joins and lexicographic products of
graphs, J. Graph Theory, N.11, 1987(3), pp. 429-440.
[8] U. Knauer, M. Nieporte, Endomorphisms of graphs I. The monoid of strong
endomorphisms, Arch. Math., N.52, 1989, pp. 607-614.
[9] W. Li, A regular endomorphism of a graph and its inverses, Mathematika, N.41,
1994, pp. 189-198.
[10] W. Li, Graphs with regular monoids, Discrete Math., N.265, 2003, pp. 105-118.
[11] W. Li, Green’s relations on the endomorphism monoid of a graph, Mathematica
Slovaca, N.45, 1995(4), pp. 335-347.
[12] W. Li, Split graphs with completely regular endomorphism monoids, Journal of
Mathematical Research and Exposition, N.26, 2006(2), pp. 253-263.
[13] W. Li, J. Chen, Endomorphism—regularity of split graphs, Europ. J. Combinatorics,
N.22, 2001, pp. 207-216.
[14] N. Pipattanajinda, Sr. Arworn, Endo-regularrity of cycle book graphs, Thai Journal
of Mathematics, N.8, 2010(3), pp. 99-104.
[15] N. Pipattanajinda, B. Gyurov, S. Panma, Path strong and cycle strong graph endo-
morphism and applications, Advances and Applications in Discrete Mathematics,
9(1) 2012, pp. 29-44.
294 The endomorphism monoids of graphs of order n
[16] N. Pipattanajinda, U. Knauer, Sr. Arworn, Endo-Regularrity of Generalized Wheel
Graphs, Chamchuri Journal of Mathematics, N.3, 2011, pp. 45-57.
[17] N. Pipattanajinda, U. Knauer, B. Gyurov, S. Panma, The endomorphism monoids
of (n − 3)-regular graphs of order n, Algebra and Discrete Mathematics, to appear.
[18] M. Petrich and N. R. Reilly, Completely reguglar semigroups, Wiley Interscience,
1999.
[19] J. Thomkeaw, Sr. Arworn, Endomorphism monoid of C2n+1 book graphs, Thai
Journal of Mathematics, N.7, 2009(2), pp. 319-327.
[20] W. Wang, H. Hou, The endomorphism monoid of N-prism, International Mathe-
matical Forum, N.6, 2011(50), pp. 2461-2471.
[21] A. Wanichsombat, Endo-completely-regular split graphs, in: Semigroups, Acts and
Categories with Applications to Graphs, Proceedings, Tartu 2007, pp. 136-142.
[22] A. Wilkeit, Graphs with regular endomorphism monoid, Arch. Math., N.66, 1996,
pp. 344-352.
Contact information
N. Pipattanajinda Program of Mathematics, Faculty of Sciences and
Technology, Kamphaeng Phet Rajabhat University,
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 Sciences,
Chiang Mai University, Chiang Mai 50200, THAI-
LAND
E-Mail(s): panmayan@yahoo.com
Received by the editors: 16.03.2012
and in final form 19.08.2013.
|