Endomorphisms of Cayley digraphs of rectangular groups
Let Cay(S,A) denote the Cayley digraph of the semigroup S with respect to the set A, where A is any subset of S. The function f : Cay(S,A) → Cay(S,A) is called an endomorphism of Cay(S,A) if for each (x, y) ∈ E(Cay(S,A)) implies (f(x), f(y)) ∈ E(Cay(S,A)) as well, where E(Cay(S,A)) is an arc set of...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2018
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/188408 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Endomorphisms of Cayley digraphs of rectangular groups / S. Arworn, B. Gyurov, N. Nupo, S. Panma // Algebra and Discrete Mathematics. — 2018. — Vol. 26, № 2. — С. 153–169. — Бібліогр.: 18 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-188408 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1884082023-02-28T01:26:51Z Endomorphisms of Cayley digraphs of rectangular groups Arworn, S. Gyurov, B. Nupo, N. Panma, S. Let Cay(S,A) denote the Cayley digraph of the semigroup S with respect to the set A, where A is any subset of S. The function f : Cay(S,A) → Cay(S,A) is called an endomorphism of Cay(S,A) if for each (x, y) ∈ E(Cay(S,A)) implies (f(x), f(y)) ∈ E(Cay(S,A)) as well, where E(Cay(S,A)) is an arc set of Cay(S,A). We characterize the endomorphisms of Cayley digraphs of rectangular groups G × L × R, where the connection sets are in the form of A = K × P × T. 2018 Article Endomorphisms of Cayley digraphs of rectangular groups / S. Arworn, B. Gyurov, N. Nupo, S. Panma // Algebra and Discrete Mathematics. — 2018. — Vol. 26, № 2. — С. 153–169. — Бібліогр.: 18 назв. — англ. 1726-3255 2010 MSC: 05C20, 05C25, 20K30, 20M99. http://dspace.nbuv.gov.ua/handle/123456789/188408 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
Let Cay(S,A) denote the Cayley digraph of the semigroup S with respect to the set A, where A is any subset of S. The function f : Cay(S,A) → Cay(S,A) is called an endomorphism of Cay(S,A) if for each (x, y) ∈ E(Cay(S,A)) implies (f(x), f(y)) ∈ E(Cay(S,A)) as well, where E(Cay(S,A)) is an arc set of Cay(S,A). We characterize the endomorphisms of Cayley digraphs of rectangular groups G × L × R, where the connection sets are in the form of A = K × P × T. |
| format |
Article |
| author |
Arworn, S. Gyurov, B. Nupo, N. Panma, S. |
| spellingShingle |
Arworn, S. Gyurov, B. Nupo, N. Panma, S. Endomorphisms of Cayley digraphs of rectangular groups Algebra and Discrete Mathematics |
| author_facet |
Arworn, S. Gyurov, B. Nupo, N. Panma, S. |
| author_sort |
Arworn, S. |
| title |
Endomorphisms of Cayley digraphs of rectangular groups |
| title_short |
Endomorphisms of Cayley digraphs of rectangular groups |
| title_full |
Endomorphisms of Cayley digraphs of rectangular groups |
| title_fullStr |
Endomorphisms of Cayley digraphs of rectangular groups |
| title_full_unstemmed |
Endomorphisms of Cayley digraphs of rectangular groups |
| title_sort |
endomorphisms of cayley digraphs of rectangular groups |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2018 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/188408 |
| citation_txt |
Endomorphisms of Cayley digraphs of rectangular groups / S. Arworn, B. Gyurov, N. Nupo, S. Panma // Algebra and Discrete Mathematics. — 2018. — Vol. 26, № 2. — С. 153–169. — Бібліогр.: 18 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT arworns endomorphismsofcayleydigraphsofrectangulargroups AT gyurovb endomorphismsofcayleydigraphsofrectangulargroups AT nupon endomorphismsofcayleydigraphsofrectangulargroups AT panmas endomorphismsofcayleydigraphsofrectangulargroups |
| first_indexed |
2025-07-16T10:26:24Z |
| last_indexed |
2025-07-16T10:26:24Z |
| _version_ |
1837798873906544640 |
| fulltext |
“adm-n4” — 2019/1/24 — 10:02 — page 153 — #3
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 26 (2018). Number 2, pp. 153–169
c© Journal “Algebra and Discrete Mathematics”
Endomorphisms of Cayley digraphs
of rectangular groups
Srichan Arworn, Boyko Gyurov,
Nuttawoot Nupo, and Sayan Panma
Communicated by V. Mazorchuk
Abstract. Let Cay(S,A) denote the Cayley digraph of
the semigroup S with respect to the set A, where A is any subset
of S. The function f : Cay(S,A) → Cay(S,A) is called an endo-
morphism of Cay(S,A) if for each (x, y) ∈ E(Cay(S,A)) implies
(f(x), f(y)) ∈ E(Cay(S,A)) as well, where E(Cay(S,A)) is an arc
set of Cay(S,A). We characterize the endomorphisms of Cayley
digraphs of rectangular groups G × L × R, where the connection
sets are in the form of A = K × P × T .
1. Introduction
Hereafter, all sets mentioned in this paper are considered to be finite.
For any semigroup S and a subset A of S, the Cayley digraph of S with
respect to the set A, denoted by Cay(S,A), is defined as the digraph with
the vertex set S and the arc set E(Cay(S,A)) = {(x, xa)|x ∈ S, a ∈ A}
(see [6]). The concept of Cayley graphs of groups is introduced by Arthur
Cayley in 1878. Many interesting results about Cayley graphs of groups
have been obtained and widely studied by various authors (see, for example,
[2], [10], [11], and [12]). In addition, Cayley digraphs of semigroups have
been considered and many new interesting results are also shown in several
journals. The class of rectangular groups is one of the famous classes
2010 MSC: 05C20, 05C25, 20K30, 20M99.
Key words and phrases: Cayley digraphs, rectangular groups, endomorphisms.
“adm-n4” — 2019/1/24 — 10:02 — page 154 — #4
154 Endomorphisms of Cayley digraphs
of semigroups and their Cayley digraphs have been studied seriously.
Moreover, some properties of the Cayley digraphs of rectangular groups,
left groups, and right groups are obtained by many authors (see, for
example, [9], [7], [13], [14], [15], [16], and [17]).
The structures of endomorphisms of Cayley digraphs of semigroups
are interesting to study. Many authors have studied some results of Cayley
digraphs of semigroups by using the properties of homomorphisms (see for
examples, [1], [4], [10], [17], and [18]). Here we shall study the structures
and give the characterizations of endomorphisms of Cayley digraphs of
rectangular groups, right groups, and left groups, respectively.
Note that the Cayley digraph of a rectangular group G× L×R with
respect to a set A = K × P × T is the disjoint union of |L| mutually
isomorphic subdigraphs, where each subdigraph is isomorphic to the
Cayley digraph of the right group G×R with respect to the set {(a, α) ∈
G×R|(a, l, α) ∈ A for some l ∈ L}. So we are specially interested in the
structure of endomorphisms of the Cayley digraph of a right group, where
the connection set is in the form of the cartesian product of sets.
As the fact that a left group G × L is one of the special cases of a
rectangular group G × L × R when |R| = 1, it makes sense to consider
their Cayley digraphs. Actually, Cayley digraphs of left groups are the
disjoint union of isomorphic copies of Cayley digraphs of groups while
Cayley digraphs of right groups are not. Moreover, Cayley digraphs of
right groups look more complicated than Cayley digraphs of left groups.
Thus we are attentive to characterize endomorphisms of Cayley digraphs
of left groups with respect to arbitrary connection sets.
The relevant notations and some terminologies related to our paper
will be given in the next section.
2. Preliminaries and notations
In this section, some preliminaries needed in what follows on digrahs
and semigroups are given. For more information on digraphs, we refer to
[3], and for semigroups see [5]. A semigroup S is called a left (right) zero
semigroup if xy = x (xy = y) for all x, y ∈ S. A semigroup S is said to be
a left (right) group if it is isomorphic to the direct product G×L (G×R)
of a group G and a left (right) zero semigroup L(R).
A semigroup S is called a band if every element in S is idempotent.
A rectangular band is a band S that satisfies xyx = x for all x, y ∈ S. In
fact, there is another classification of rectangular bands. A semigroup S
is said to be a rectangular band if it is isomorphic to the direct product
“adm-n4” — 2019/1/24 — 10:02 — page 155 — #5
S. Arworn, B. Gyurov, N. Nupo, S. Panma 155
L×R of a left zero semigroup L and a right zero semigroup R. Moreover,
a semigroup S is called a rectangular group if it is isomorphic to the direct
product G × L × R of a group G and a rectangular band L × R. It is
obvious that a left (right) zero semigroup, a left (right) group, and a
rectangular band are all rectangular groups.
A digraph (directed graph) D = (V,E) is a set V = V (D) of vertices
together with a binary relation E = E(D) on V . The elements e = (u, v)
of E are called the arcs of D (see [3]).
Let D1 = (V1, E1) and D2 = (V2, E2) be digraphs. As in [8], a digraph
homomorphism f : D1 → D2 is a mapping f : V1 → V2 such that
(u, v) ∈ E1 implies (f(u), f(v)) ∈ E2 for all u, v ∈ V1. In other words, the
digraph homomorphism f is also said to be edge-preserving. The digraph
homomorphism f : D → D is called an endomorphism of D and we denote
by End(D) the monoid of all endomorphisms of D.
From now on, |A| denotes the cardinality of A, where A is any finite
set and pi denotes the projection map on the ith coordinate of a triple
where i ∈ {1, 2, 3}. A subdigraph F of a digraph G is called a strong
subdigraph of G if and only if whenever u and v are vertices of F and
(u, v) is an arc in G, then (u, v) is an arc in F as well.
3. Main results
In this section, we present the results about endomorphisms of Cayley
digraphs of some rectangular groups. We divide this section into three parts.
In the first part, we give some results for endomorphisms of Cayley digraphs
of rectangular groups and the remaining parts show some characterizations
of endomorphisms of Cayley digraphs of right groups and left groups,
respectively.
In order to study the structure of endomorphisms of Cayley digraphs
of rectangular groups, we need to prescribe some notations used in what
follows. For any digraph Ω and X ⊆ V (Ω), by [X], we mean the strong
subdigraph of Ω induced by X. For each function f : Ω1 −→ Ω2 from
a digraph Ω1 to a digraph Ω2 and any subdigraph Σ of Ω1, we mention
f(Σ) as a strong subdigraph [f(V (Σ))] of Ω2 induced by f(V (Σ)). We
now study the endomorphisms of Cayley digraphs of rectangular groups.
3.1. Endomorphisms of Cayley digraphs of rectangular groups
Throughout this part, we let S = G× L×R be a rectangular group
and D = Cay(S,A) the Cayley digraph of the semigroup S with respect
“adm-n4” — 2019/1/24 — 10:02 — page 156 — #6
156 Endomorphisms of Cayley digraphs
to the set A. Before we give some results of endomorphisms of Cayley
digraphs of rectangular groups, we first define a useful function using in
the sequel.
Let f : S → S be a function and l ∈ L. For each α ∈ R, we define
Φlα : G → G by
Φlα(a) = b if there exist t ∈ L and β ∈ R
such that f(a, l, α) = (b, t, β) for all a ∈ G.
It is easy to verify that Φlα is well-defined. We now present some results
about endomorphisms of Cayley digraphs of rectangular groups with
respect to the given connection sets.
Theorem 3.1. Let A = K × P × T be the connection set of D and
f : S → S be a function. Then f ∈ End(D) if and only if for each l ∈ L,
the following conditions hold:
(i) f([b〈K〉 × {l} × R]) is a subdigraph of [c〈K〉 × {t} × R] for some
t ∈ L, c ∈ G and for all b ∈ G;
(ii) Φlα ∈ End(Cay(G,K)) for all α ∈ T ;
(iii) for each g ∈ K and a ∈ G, there exists ga ∈ K such that
f(ag−1, l, θ) ∈
{
{Φlλ(a)g
−1
a } × {u} × T if θ ∈ T,
{Φlλ(a)g
−1
a } × {u} ×R if θ ∈ R \ T
for all λ ∈ T and for some u ∈ L.
Proof. Let A = K×P×T be the connection set of D, l ∈ L and f : S → S
be a function.
(⇒) Assume that f ∈ End(D). Let b ∈ G. We first show that f([b〈K〉×
{l} × R]) is a subdigraph of [c〈K〉 × {t} × R] for some t ∈ L andc ∈ G.
Let (g, p, r), (h, k, s) be two vertices of f([b〈K〉 × {l} × R]) such that
(g, p, r) ∈ c〈K〉×{t}×R and (h, k, s) ∈ d〈K〉×{u}×R for some t, u ∈ L
and c, d ∈ G. Thus p = t and k = u and hence
(g, t, r) = (g, p, r) = f(g′, p′, r′)
for some (g′, p′, r′) ∈ b〈K〉 × {l} ×R and
(h, u, s) = (h, k, s) = f(h′, k′, s′)
for some (h′, k′, s′) ∈ b〈K〉 × {l} ×R. Then p′ = l = k′. Since
((g′, l, r′), (g′, l, r′)(a, i, x)) ∈ E(D),
“adm-n4” — 2019/1/24 — 10:02 — page 157 — #7
S. Arworn, B. Gyurov, N. Nupo, S. Panma 157
where (a, i, x) ∈ A and f ∈ End(D), we have
(f(g′, l, r′), f(g′a, l, x)) ∈ E(D).
Similarly, we conclude that ((h′, l, s′), (h′, l, s′)(a, i, x)) ∈ E(D) implies
(f(h′, l, s′), f(h′a, l, x)) ∈ E(D). From g′, h′ ∈ b〈K〉 and a ∈ K, we get
g′a, h′a ∈ b〈K〉. Consider the strong subdigraph [b〈K〉 × {l} × {x}] of D.
Since [b〈K〉 × {l} × {x}] is isomorphic to Cay(〈K〉,K), and Cay(〈K〉,K)
is connected, we obtain that there exists a dipath connecting between
(g′a, l, x) and (h′a, l, x), say the dipath M . We may assume that
M := (g′a, l, x),m1,m2, . . . ,mq, (h
′a, l, x),
where mj ∈ b〈K〉 × {l} × {x} and j = 1, 2, . . . , q. Since f ∈ End(D), we
have
f(g′a, l, x), f(m1), f(m2), . . . , f(md), f(h
′a, l, x)
is a diwalk in D. Hence there exists a semi-diwalk connecting between
f(g′, p′, r′) and f(h′, k′, s′). Since [c〈K〉 × {t} ×R] and [d〈K〉 × {u} ×R]
are maximal semi-connected subdigraphs of D, we conclude that
[c〈K〉 × {t} ×R] = [d〈K〉 × {u} ×R],
that is, t = u. Therefore, V (f([b〈K〉 × {l} ×R])) ⊆ c〈K〉 × {t} ×R. We
now let ((g1, t1, r1), (g2, t2, r2)) ∈ E(f([b〈K〉 × {l} ×R])). Then
(g1, t1, r1), (g2, t2, r2) ∈ V (f([b〈K〉 × {l} ×R])) ⊆ c〈K〉 × {t} ×R.
Thus ((g1, t1, r1), (g2, t2, r2)) ∈ E([c〈K〉×{t}×R]) since [c〈K〉×{t}×R]
is a strong subdigraph of D. Consequently, f([b〈K〉 × {l} × R]) is a
subdigraph of [c〈K〉 × {t} ×R].
Next, we will prove that Φlα ∈ End(Cay(G,K)) for all α ∈ T . Let α ∈
T and (x, y) ∈ E(Cay(G,K)). Thus y = xa for some a ∈ K. Assume that
Φlα(x) = u and Φlα(y) = v for some u, v ∈ G. Then f(x, l, α) = (u, k, β)
and f(y, l, α) = (v, q, γ) for some k, q ∈ L and β, γ ∈ R. Since
((x, l, α), (y, l, α)) = ((x, l, α), (xa, l, α))
= ((x, l, α), (x, l, α)(a, p, α)) ∈ E(D),
where (a, p, α)) ∈ A and f ∈End(D), we have (f(x, l, α), f(y, l, α))∈E(D),
that is, f(y, l, α) = f(x, l, α)(b,m, λ) for some (b,m, λ) ∈ A. Hence
(v, q, γ) = f(y, l, α) = f(x, l, α)(b,m, λ) = (u, k, β)(b,m, λ) = (ub, k, λ).
“adm-n4” — 2019/1/24 — 10:02 — page 158 — #8
158 Endomorphisms of Cayley digraphs
We obtain that v = ub that means Φlα(y) = v = ub = Φlα(x)b, where
b ∈ K. Therefore, (Φlα(x),Φlα(y)) ∈ E(Cay(G,K)) and then Φlα ∈
End(Cay(G,K)).
Now, we will prove (iii). Let λ ∈ T and θ ∈ R. For each g ∈ K and
a ∈ G, consider (ag−1, l, θ) ∈ S. Since (a, l, λ) = (ag−1, l, θ)(g, p, λ), where
(g, p, λ) ∈ A, we get ((ag−1, l, θ), (a, l, λ)) ∈ E(D). Because f ∈ End(D),
we obtain that (f(ag−1, l, θ), f(a, l, λ)) ∈ E(D). We may assume
that f(ag−1, l, θ) = (h, u, δ) for some (h, u, δ) ∈ S. Then there exists
(ga, i, µ) ∈ A such that
f(a, l, λ) = f(ag−1, l, θ)(ga, i, µ) = (h, u, δ)(ga, i, µ) = (hga, u, µ).
Hence Φlλ(a) = hga. Therefore, f(ag−1, l, θ) = (h, u, δ) = (hgag
−1
a , u, δ) =
(Φlλ(a)g
−1
a , u, δ).
If θ ∈ T , then (g, p, θ) ∈ A. Since (ag−1, l, θ) = (ag−2, l, θ)(g, p, θ), we
obtain that ((ag−2, l, θ), (ag−1, l, θ)) ∈ E(D). Since f ∈ End(D), we have
(f(ag−2, l, θ), f(ag−1, l, θ)) ∈ E(D). Suppose that f(ag−2, l, θ) = (c, e, ε)
for some (c, e, ε) ∈ S. Hence
f(ag−1, l, θ) = f(ag−2, l, θ)(m,w, η) = (c, e, ε)(m,w, η) = (cm, e, η)
for some (m,w, η) ∈ A. So we can conclude that (Φlλ(a)g
−1
a , u, δ) =
(cm, e, η) and hence δ = η ∈ T . Therefore,
f(ag−1, l, θ) ∈
{
{Φlλ(a)g
−1
a } × {u} × T if θ ∈ T,
{Φlλ(a)g
−1
a } × {u} ×R if θ ∈ R \ T.
(⇐) Suppose that the conditions hold. We will prove that f ∈ End(D).
Let ((a, l, ρ), (b, j, λ)) ∈ E(D). Thus there exists (k, p, t) ∈ A such that
(b, j, λ) = (a, l, ρ)(k, p, t) = (ak, l, t). Then b = ak, j = l and λ = t ∈ T .
Since (a, b) = (a, ak) ∈ E(Cay(G,K)) and Φlλ ∈ End(Cay(G,K)), we get
that (Φlλ(a),Φlλ(b)) ∈ E(Cay(G,K)). Hence Φlλ(b) = Φlλ(a)c for some
c ∈ K. By condition (iii), there exist u ∈ L, µ ∈ R and q ∈ K in which
f(a, l, ρ) = f(akk−1, l, ρ) = (Φlλ(ak)q
−1, u, µ)
= (Φlλ(b)q
−1, u, µ) = (Φlλ(a)cq
−1, u, µ).
By the definition of Φlλ, there exist m ∈ L and ω ∈ R such that f(b, j, λ) =
f(b, l, λ) = (Φlλ(b),m, ω). Since λ = t ∈ T , again by condition (iii), we can
conclude that there exists s ∈ K such that f(b, j, λ) = f(bnn−1, j, λ) =
(Φjλ(bn)s
−1, v, ξ) for some n ∈ K, v ∈ L and ξ ∈ T . Thus ω = ξ ∈ T
“adm-n4” — 2019/1/24 — 10:02 — page 159 — #9
S. Arworn, B. Gyurov, N. Nupo, S. Panma 159
and hence f(b, j, λ) = (Φlλ(b),m, ω) = (Φlλ(a)c,m, ω). Since j = l and
((a, l, ρ), (b, j, λ)) ∈ E(D), we gain that (a, l, ρ), (b, j, λ) ∈ g〈K〉 × {l} ×R
for some g ∈ G. We get that f(a, l, ρ), f(b, j, λ) ∈ V (f([g〈K〉 × {l}×R])).
Since f([g〈K〉 × {l} ×R]) is a subdigraph of [h〈K〉 × {p} ×R] for some
h ∈ G and p ∈ L, both of f(a, l, ρ), f(b, j, λ) must belong to the vertex set
of the same strong subdigraph of D. From f(a, l, ρ) = (Φlλ(a)cq
−1, u, µ)
and f(b, j, λ) = (Φlλ(b),m, ω), we can conclude that f(a, l, ρ), f(b, j, λ) ∈
d〈K〉 × {u} ×R for some d ∈ G that means m = u. For fixed y ∈ P , we
have (q, y, ω) ∈ K × P × T = A and then
f(b, j, λ) = (Φlλ(a)c,m, ω) = (Φlλ(a)c, u, ω)
= (Φlλ(a)cq
−1, u, µ)(q, y, ω)
= f(a, l, ρ)(q, y, ω).
Hence (f(a, l, ρ), f(b, j, λ)) ∈ E(D) and thus f ∈ End(D), as required.
Now, we will illustrate an example of an endomorphism of the Cayley
digraph of a rectangular group with respect to the set A as stated in
Theorem 3.1 and indicate that the endomorphism satisfies three conditions
as shown in Theorem 3.1.
Example 3.2. Let D = Cay(Z3 × {l, k} × {α, β}, A), where A = {1} ×
{l} × {α}.
b b b b b b
b b b b b b
0lα 1lα 2lα 0kα 1kα 2kα
0lβ 1lβ 2lβ 0kβ 1kβ 2kβ
Figure 1. Cay(Z3 × {l, k} × {α, β}, A).
We obtain that
f =
(
0lα 1lα 2lα 0kα 1kα 2kα 0lβ 1lβ 2lβ 0kβ 1kβ 2kβ
1kα 2kα 0kα 2lα 0lα 1lα 1kβ 2kα 0kα 2lβ 0lβ 1lβ
)
∈ End(D).
From p1(A) = {1}, we have 〈p1(A)〉 = {0, 1, 2}. Consider f(〈p1(A)〉×{l}×
{α, β}) = {1kα, 2kα, 0kα, 1kβ}, we get that the digraph f([〈p1(A)〉×{l}×
“adm-n4” — 2019/1/24 — 10:02 — page 160 — #10
160 Endomorphisms of Cayley digraphs
b b b
b
0kα 1kα 2kα
1kβ
Figure 2. Digraph [{0kα, 1kα, 2kα, 1kβ}].
{α, β}]) = [{1kα, 2kα, 0kα, 1kβ}] shown in Figure 2 is the subdigraph of
[〈p1(A)〉 × {k} × {α, β}].
Similarly, we can observe that f([〈p1(A)〉 × {k} × {α, β}]) is a subdi-
graph of [〈p1(A)〉 × {l} × {α, β}]. Moreover, we have
Φlα =
(
0 1 2
1 2 0
)
and Φkα =
(
0 1 2
2 0 1
)
and both of them are endomorphisms of Cay(Z3, {1}). In addition, f
satisfies the condition (iii) in Theorem 3.1 as shown as follows:
f(0+1−1, l, α) = f(2, l, α) = (0, k, α)=(1+2, k, α)=(Φlα(0)+1−1, k, α),
f(1+1−1, l, α) = f(0, l, α) = (1, k, α)=(2+2, k, α)=(Φlα(1)+1−1, k, α),
f(2+1−1, l, α) = f(1, l, α) = (2, k, α)=(0+2, k, α)=(Φlα(2)+1−1, k, α),
f(0+1−1, k, α) = f(2, k, α) = (1, l, α)=(2+2, l, α)=(Φkα(0)+1−1, l, α),
f(1+1−1, k, α) = f(0, k, α) = (2, l, α)=(0+2, l, α)=(Φkα(1)+1−1, l, α),
f(2+1−1, k, α) = f(1, k, α) = (0, l, α)=(1+2, l, α)=(Φkα(2)+1−1, l, α).
Similarly,for each t ∈ {l, k}, we have f(x+ 1−1, t, β) ∈ {Φtα(x) + 1−1} ×
{u} ×R for all x ∈ Z3 and for some u ∈ {l, k}.
The next proposition describes the relation between two useful map-
pings for studying an endomorphism of the Cayley digraph of a rectangular
group with respect to the set mentioned in the above theorem via an
edge-preserving property. Before we show the result, we need to define
the notation for convenience to use in the proof.
Notation 3.3. Let f : D → D, l ∈ L and α ∈ R. We denote the
restriction function f|G×{l}×{α}
: [G× {l} × {α}] → D by fGlα.
“adm-n4” — 2019/1/24 — 10:02 — page 161 — #11
S. Arworn, B. Gyurov, N. Nupo, S. Panma 161
Proposition 3.4. Let A = K × P × T be the connection set of D. For
each l ∈ L and α ∈ T , Φlα ∈ End(Cay(G,K)) if and only if p1 ◦ fGlα :
[G× {l} × {α}] → Cay(G,K) is a homomorphism.
Proof. Let l ∈ L and α ∈ T . Suppose that Φlα ∈ End(Cay(G,K)). Let
g, h ∈ G be such that ((g, l, α), (h, l, α)) ∈ E(D). Then there exists
(a, q, λ) ∈ A such that (h, l, α) = (g, l, α)(a, q, λ) = (ga, l, λ), that is, h =
ga, where a ∈ K. This implies that (g, h) ∈ E(Cay(G,K)). Since Φlα is an
endomorphism of Cay(G,K), we have (Φlα(g),Φlα(h)) ∈ E(Cay(G,K)).
We may assume that Φlα(g) = x and Φlα(h) = y for some x, y ∈ G. Thus
fGlα(g, l, α) = f(g, l, α) = (x, t, µ)
and
fGlα(h, l, α) = f(h, l, α) = (y, s, η)
for some s, t ∈ L and µ, η ∈ R. Hence
(p1 ◦ fGlα)(h, l, α) = y = Φlα(h) = Φlα(g)k = xk = (p1 ◦ fGlα)(g, l, α)k,
where k ∈ K. Then ((p1 ◦fGlα)(g, l, α), (p1 ◦fGlα)(h, l, α)) ∈ E(D). There-
fore, p1 ◦ fGlα is a homomorphism.
Conversely, assume that p1◦fGlα is a homomorphism. We will show that
Φlα ∈ End(Cay(G,K)). Let x, y ∈ G be such that (x, y) ∈ E(Cay(G,K)).
Thus y = xa for some a ∈ K. Since α ∈ T , there exists u ∈ P in which
(a, u, α) ∈ A because A = K × P × T . Hence (y, l, α) = (xa, l, α) =
(x, l, α)(a, u, α) and then ((x, l, α), (y, l, α)) ∈ E(D). By our assumption,
we obtain that
((p1 ◦ fGlα)(x, l, α), (p1 ◦ fGlα)(y, l, α)) ∈ E(Cay(G,K)).
We will take f(x, l, α) = (x′, l′, α′) and f(y, l, α) = (y′, l′, α′) for some
(x′, l′, α′),
(y′, l′, α′) ∈ S. Hence Φlα(x) = x′ and Φlα(y) = y′. We can conclude that
(Φlα(x),Φlα(y)) = (x′, y′)
= ((p1 ◦ fGlα)(x, l, α), (p1 ◦ fGlα)(y, l, α)) ∈ E(Cay(G,K)).
Consequently, Φlα ∈ End(Cay(G,K)).
“adm-n4” — 2019/1/24 — 10:02 — page 162 — #12
162 Endomorphisms of Cayley digraphs
3.2. Endomorphisms of Cayley digraphs of right groups
All over this subsection, we let S = G×R be a right group which is
isomorphic to a rectangular group G× L×R when L = {l}. Denote by
D the Cayley digraph Cay(S,A) of the semigroup S with respect to the
set A.
We first define the gainful function using in this subsection before
we present some results of endomorphisms of Cayley digraphs of right
groups. For each α ∈ R and for all a ∈ G, we define ϕα : G → G by
ϕα(a) = Φlα(a), where Φlα is the function defined in Subsection 3.1 with
L = {l}.
In fact, for convenience, we can consider ϕα in another expression as
follows.
Let f : S → S be a function. For each α ∈ R and for all a ∈ G, we
define ϕα : G → G by
ϕα(a) = b if there exists β ∈ R such that f(a, α) = (b, β).
It is not hard to examine that ϕα is well-defined. We now show some
results about endomorphisms of Cayley digraphs of right groups with
respect to some connection sets.
Theorem 3.5. Let A = K × T be a connection set of D and f : S → S
be a function. Then f ∈ End(D) if and only if the following conditions
hold:
(i) ϕα ∈ End(Cay(G,K)) for all α ∈ T ;
(ii) for each g ∈ K and a ∈ G, there exists ga ∈ K such that
f(ag−1, θ) ∈
{
{ϕλ(a)g
−1
a } × T if θ ∈ T,
{ϕλ(a)g
−1
a } ×R if θ ∈ R \ T
for all λ ∈ T .
Proof. (⇒) Actually, G×R is isomorphic to G×L×R when |L| = 1. So
the result is clear by Theorem 3.1.
(⇐) Without loss of generality, suppose that S = G× L×R, where
L is a one-element left zero semigroup. Clearly, condition (i) of Theorem
3.1 holds for S and K × T . On the other hand, since |L| = 1, conditions
(ii) and (iii) of Theorem 3.1 hold by the assumption.
We now present an example of an endomorphism of the Cayley digraph
of a right group with respect to the set mentioned in Theorem 3.5.
“adm-n4” — 2019/1/24 — 10:02 — page 163 — #13
S. Arworn, B. Gyurov, N. Nupo, S. Panma 163
Example 3.6. Let D = Cay(Z6 × {α, β}, A), where A = {2} × {α}.
b b b b b b
b b b b b b
0α 1α 2α 3α 4α 5α
0β 1β 2β 3β 4β 5β
Figure 3. Cay(Z6 × {α, β}, A).
We obtain that
f =
(
0α 1α 2α 3α 4α 5α 0β 1β 2β 3β 4β 5β
5α 3α 1α 5α 3α 1α 5β 3α 1α 5α 3β 1α
)
∈ End(D).
Moreover, we have
ϕα =
(
0 1 2 3 4 5
5 3 1 5 3 1
)
∈ End(Cay(Z6, {2})).
In addition, f satisfies the condition (ii) in Theorem 3.5 as shown as
follows:
f(0 + 2−1, α) = f(4, α) = (3, α) = (5 + 4, α) = (ϕα(0) + 2−1, α),
f(1 + 2−1, α) = f(5, α) = (1, α) = (3 + 4, α) = (ϕα(1) + 2−1, α),
f(2 + 2−1, α) = f(0, α) = (5, α) = (1 + 4, α) = (ϕα(2) + 2−1, α),
f(3 + 2−1, α) = f(1, α) = (3, α) = (5 + 4, α) = (ϕα(3) + 2−1, α),
f(4 + 2−1, α) = f(2, α) = (1, α) = (3 + 4, α) = (ϕα(4) + 2−1, α),
f(5 + 2−1, α) = f(3, α) = (5, α) = (1 + 4, α) = (ϕα(5) + 2−1, α).
Similarly, we have f(x+ 2−1, β) ∈ {ϕα(x) + 2−1} ×R for all x ∈ Z6.
To illustrate the structure of endomorphisms of Cayley digraphs of
right groups, we consider the following special connection sets.
Corollary 3.7. Let A = {g} ×R be a connection set of D, where g ∈ G,
and f : S → S be a function. Then f ∈ End(D) if and only if the following
conditions hold:
(i) ϕα ∈ End(Cay(G, {g})) for all α ∈ R;
(ii) ϕβ = ϕγ for all β, γ ∈ R.
“adm-n4” — 2019/1/24 — 10:02 — page 164 — #14
164 Endomorphisms of Cayley digraphs
Proof. Suppose that f ∈ End(D). By condition (i) of Theorem 3.5, we
have ϕα ∈ End(Cay(G, {g})) for all α ∈ R. Let a ∈ G. By Theorem
3.5(ii), we obtain that
ϕβ(a)g
−1 = f(ag−1, θ) = ϕγ(a)g
−1 for all β, γ ∈ R.
Therefore, ϕβ = ϕγ for all β, γ ∈ R.
Conversely, suppose that ϕβ = ϕγ for all β, γ ∈ R. Let a ∈ G and θ ∈ R.
Since (ag−1, a) ∈ E(Cay(G, {g})) and ϕθ ∈ End(Cay(G, {g})), we obtain
that (ϕθ(ag
−1), ϕθ(a)) ∈ E(Cay(G, {g})). Hence ϕθ(a) = ϕθ(ag
−1)g and
this implies that ϕθ(ag
−1) = ϕθ(a)g
−1. Since ϕθ = ϕλ for all λ ∈ R as we
supposed above, we can conclude that ϕθ(ag
−1) = ϕλ(a)g
−1. Therefore,
there exists µ ∈ R such that f(ag−1, θ) = (ϕλ(a)g
−1, µ) for all λ ∈ R. By
the converse of Theorem 3.5, we obtain that f ∈ End(D).
Furthermore, the number of endomorphisms of the Cayley digraph of
a right group with respect to the set {g} ×R is obtained in the following
proposition.
Proposition 3.8. Let G be a group of order n and R be a right zero
semigroup of order m. Let A = {g} ×R be a connection set of D where
g ∈ G.
If |End(Cay(G, {g}))| = d for some d ∈ N, then |End(D)| = d ·mmn.
Proof. In order to construct an endomorphism f of D, let φ ∈
End(Cay(G, {g})) be fixed. Let β ∈ R and define f : S → S as follows for
every (x, α) ∈ S:
f(x, α) = (φ(x), β).
Now by Corollary 3.7, f is an endomorphism of D. It can be easily
seen that β is arbitrary, this means that it does not matter when we
choose whatever β ∈ R, the function f is always an endomorphism of
D. So we can conclude that for each φ ∈ End(Cay(G, {g})) and for each
(x, α) ∈ S, we have m ways to construct endomorphisms of D. On the
other hand, if we pick f ∈ End(D), we can obtain by Corollary 3.7 that
f must be one of those functions that we defined above. Consequently,
|End(D)| = |End(Cay(G, {g}))||R||S| = d ·mmn, as required.
3.3. Endomorphisms of Cayley digraphs of left groups
Throughout this subsection, we let S = G × L be a left group and
D = Cay(S,A) the Cayley digraph of the semigroup S with respect to
the set A.
“adm-n4” — 2019/1/24 — 10:02 — page 165 — #15
S. Arworn, B. Gyurov, N. Nupo, S. Panma 165
Before we present the characterization of endomorphisms of Cayley
digraphs of rectangular groups, we will define the notation for convenience
in using.
Let G/〈p1(A)〉 = {g1〈p1(A)〉, g2〈p1(A)〉, . . . , gk〈p1(A)〉} where gi ∈ G
for all i ∈ I = {1, 2, . . . , k}. Let f : S → S be a function and l ∈ L. By
fil, we mean the restriction function f|gi〈p1(A)〉×{l}
: [gi〈p1(A)〉 × {l}] → D,
where [gi〈p1(A)〉 × {l}] is the strong subdigraph of D.
Theorem 3.9. Let f : G×L → G×L be a function and A be a subset of
G× L. For the Cayley digraph D = Cay(G× L,A), following conditions
are equivalent:
(i) f ∈ End(D);
(ii) fil is edge-preserving for all l ∈ L and i ∈ I;
(iii) for each (x, l) ∈ G× L and a ∈ p1(A),
f(xa, l) = (p1(f(x, l))b, p2(f(x, l)))
for some b ∈ p1(A).
Proof. Let A be a connection set of D and f : D → D.
(i)⇒(ii) Suppose that f ∈ End(D). Let l ∈ L and i ∈ I. We will prove
that fil is edge-preserving. Let ((x, l), (y, l)) ∈ E([gi〈p1(A)〉 × {l}]). Then
((x, l), (y, l)) ∈ E(D). We have (fil(x, l), fil(y, l)) = (f(x, l), f(y, l)) ∈
E(D) since f ∈ End(D). Therefore, fil is edge-preserving, as required.
(ii)⇒(iii) Assume that (ii) is true. Let (x, l) ∈ G× L and a ∈ p1(A).
Then (x, l) ∈ gi〈p1(A)〉 × {l} for some i ∈ I. Thus there exists l′ ∈
p2(A) such that (a, l′) ∈ A. Consider (xa, l) = (x, l)(a, l′), we obtain that
((x, l), (xa, l)) ∈ E([gi〈p1(A)〉× {l}]) ⊆ E(D). Since fil is edge-preserving,
we can get that (f(x, l), f(xa, l)) = (fil(x, l), fil(xa, l)) ∈ E(D). Suppose
that f(x, l) = (y, l1) for some (y, l1) ∈ G×L. Then there exists (b, l2) ∈ A
such that
f(xa, l) = f(x, l)(b, l2) = (y, l1)(b, l2) = (yb, l1)
= (p1(f(x, l))b, p2(f(x, l))),
where b ∈ p1(A).
(iii)⇒(i) Suppose that the statement (iii) holds. We will show that
f ∈ End(D). Let ((x, l1), (y, l2)) ∈ E(D). Thus (y, l2) = (x, l1)(a, l3) =
(xa, l1) for some (a, l3) ∈ A. Hence y = xa and l1 = l2. Assume that
f(x, l1) = (u, l4) for some (u, l4) ∈ G× L. By our supposition, we have
f(y, l2) = f(xa, l1) = (p1(f(x, l1))b, p2(f(x, l1))) = (ub, l4)
“adm-n4” — 2019/1/24 — 10:02 — page 166 — #16
166 Endomorphisms of Cayley digraphs
for some b1 ∈ p1(A). Since b ∈ p1(A), there exists l5 ∈ p2(A) such
that (b, l5) ∈ A. We obtain that f(y, l2) = (ub, l4) = (u, l4)(b, l5) =
f(x, l1)(b, l5), that is, (f(x, l1), f(y, l2)) ∈ E(D). Therefore, f ∈ End(D).
The above theorem presents characterizations of endomorphisms of
Cayley digraphs of left groups. It is more general than Theorem 3.1 in the
case of left groups since the connection sets considered in Theorem 3.9 are
arbitrary. The last example is presented for guaranteeing the properties of
endomorphisms of Cayley digraphs of left groups with respect to arbitrary
connection sets.
Example 3.10. Let D = Cay(Z6 × {l, k}, A), where A = {(2, l)}.
b b b b b b
b b b b b b
0l 1l 2l 3l 4l 5l
0k 1k 2k 3k 4k 5k
Figure 4. Cay(Z6 × {l, k}, A).
We obtain that
f =
(
0l 1l 2l 3l 4l 5l 0k 1k 2k 3k 4k 5k
1k 2l 3k 4l 5k 0l 3l 5l 5l 1l 1l 3l
)
∈ End(D).
Since 〈p1(A)〉 = 〈{2}〉 = {0, 2, 4}, if we let g1 = 0 and g2 = 1, we obtain
that
(g1 + 〈p1(A)〉)× {l} = {(0, l), (2, l), (4, l)};
(g1 + 〈p1(A)〉)× {k} = {(0, k), (2, k), (4, k)};
(g2 + 〈p1(A)〉)× {l} = {(1, l), (3, l), (5, l)}
and
(g2 + 〈p1(A)〉)× {k} = {(1, k), (3, k), (5, k)}.
We can conclude that
f1l =
(
0l 2l 4l
1k 3k 5k
)
and f1k =
(
0k 2k 4k
3l 5l 1l
)
;
“adm-n4” — 2019/1/24 — 10:02 — page 167 — #17
S. Arworn, B. Gyurov, N. Nupo, S. Panma 167
f2l =
(
1l 3l 5l
2l 4l 0l
)
and f2k =
(
1k 3k 5k
5l 1l 3l
)
and they are edge-preserving.
The following computation shows that the endomorphism f defined
as above satisfies the third condition in Theorem 3.9.
f(0 + 2, l) = f(2, l) = (3, k) = (1 + 2, k) = (p1(f(0, l)) + 2, p2(f(0, l))),
f(1 + 2, l) = f(3, l) = (4, l) = (2 + 2, l) = (p1(f(1, l)) + 2, p2(f(1, l))),
f(2 + 2, l) = f(4, l) = (5, k) = (3 + 2, k) = (p1(f(2, l)) + 2, p2(f(2, l))),
f(3 + 2, l) = f(5, l) = (0, l) = (4 + 2, l) = (p1(f(3, l)) + 2, p2(f(3, l))),
f(4 + 2, l) = f(0, l) = (1, k) = (5 + 2, k) = (p1(f(4, l)) + 2, p2(f(4, l))),
f(5 + 2, l) = f(1, l) = (2, l) = (0 + 2, l) = (p1(f(5, l)) + 2, p2(f(5, l))).
Similarly, we obtain that f(x+ 2, k) = (p1(f(x, k)) + 2, p2(f(x, k))) for
all x ∈ Z6.
4. Conclusion
In this paper, we have provided related backgrounds of the research and
some preliminaries together with notations in section 1 and section 2, re-
spectively. In the third section, some characterizations of endomorphisms
of Cayley digraphs of rectangular groups with respect to appropriate
connection sets are obtained. In addition, we illustrated examples of en-
domorphisms of Cayley digraphs of those rectangular groups to guarantee
our results.
Acknowledgements
We would like to thank the referee(s) for comments and suggestions on
the manuscript. This research was supported by Chiang Mai University.
References
[1] Bauslaugh B. L., Homomorphisms of infinite directed graphs, Ph.D. Thesis, Simon
Fraser University, 1994, 1-132.
[2] Biggs N., Algebraic Graph Theory, Cambridge University Press, Cambridge, 1993.
[3] Bondy J. A., Murty U. S. R., Graph Theory with applications, American Elsevier
Publishing Co., INC, New York, 1976.
[4] Cameron P. J., Graph homomorphisms, Combinatorics Study Group Notes, 2006.
[5] Howie J. M., Fundamentals of semigroup theory, Clarendon Press, Oxford, 1995.
“adm-n4” — 2019/1/24 — 10:02 — page 168 — #18
168 Endomorphisms of Cayley digraphs
[6] Kelarev A. V., On undirected Cayley graphs, Australas. J. Combin., Vol. 25, 2002,
73-78.
[7] Khosravi B., On Cayley graphs of left groups, Houston J. Math., Vol. 35, No. 3,
2009, 745-755.
[8] Khosravi B. and Khosravi B., A characterization of Cayley graphs of Brandt
semigroups, Bull. Malays. Math. Sci. Soc., Vol. 35, 2012, 399-410.
[9] Khosravi B., Mahmoudi M., On Cayley graphs of rectangular groups, Discrete
Math., Vol. 310, 2010, 804-811.
[10] Knauer U., Algebraic graph theory, W. de Gruyter, Berlin, 2011.
[11] Li C. H., Isomorphisms of connected Cayley graphs, Graphs Combin., Vol. 14,
1998, 37-44.
[12] Li C. H., On isomorphisms of finite Cayley graphs - a survey, Discrete Math., Vol.
256, 2002, 301-334.
[13] Meksawang J., Panma S., Isomorphism conditions for Cayley graphs of rectangular
groups, Bull. Malays. Math. Sci. Soc., Vol. 39, 2016, 29-41.
[14] Panma S., Characterization of Cayley graphs of rectangular groups, Thai J. Math.,
Vol. 8, No. 3, 2010, 535-543.
[15] Panma S., Knauer U., Arworn Sr., On transitive Cayley graphs of right (left)
groups and of Clifford semigroups, Thai J. Math., Vol. 2, 2004, 183-195.
[16] Panma S., Knauer U., Arworn Sr., On transitive Cayley graphs of strong semilattice
of right (left) groups, Discrete Math., Vol. 309, 2009, 5393-5403.
[17] Ruangnai M., Panma S., Arworn Sr., On Cayley isomorphisms of left and right
groups, Int. J. of Pure and Applied Math., Vol. 80, No. 4, 2012, 561-571.
[18] Shurbert D., An introduction to graph homomorphisms, University of Puget Sound,
2013, 1-12.
Contact information
Srichan Arworn,
Nuttawoot Nupo
Department of Mathematics, Chiang Mai
University,
Huay Kaew Road, Chiang Mai, Thailand, 50200
E-Mail(s): srichan28@yahoo.com,
nuttawoot_nupo@cmu.ac.th
Boyko Gyurov School of Science and Technology Georgia
Gwinnett College
1000 University Center Lane Lawrenceville, GA
30043
E-Mail(s): bgyurov@ggc.edu
“adm-n4” — 2019/1/24 — 10:02 — page 169 — #19
S. Arworn, B. Gyurov, N. Nupo, S. Panma 169
Sayan Panma Center of Excellence in Mathematics and
Applied Mathematics,
Department of Mathematics, Faculty of Science,
Chiang Mai University, Chiang Mai 50200,
Thailand
E-Mail(s): panmayan@yahoo.com
Received by the editors: 11.01.2017
and in final form 09.12.2018.
|