Characterization of finite simple semigroup digraphs
This paper characterizes directed graphs which are Cayley graphs of finite simple semigroups, i.e. of a subspecies of completely regular semigroups. Moreover we investigate the structure of Cayley graphs of finite simple semigroups with a one-element connection set. We introduce the conditions for w...
Збережено в:
| Дата: | 2011 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2011
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/154770 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Characterization of finite simple semigroup digraphs / J. Meksawang, S. Panma, U. Knauer // Algebra and Discrete Mathematics. — 2011. — Vol. 12, № 1. — С. 53–68. — Бібліогр.: 16 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-154770 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1547702019-06-16T01:32:29Z Characterization of finite simple semigroup digraphs Meksawang, J. Panma, S. Knauer, U. This paper characterizes directed graphs which are Cayley graphs of finite simple semigroups, i.e. of a subspecies of completely regular semigroups. Moreover we investigate the structure of Cayley graphs of finite simple semigroups with a one-element connection set. We introduce the conditions for which they are isomorphic and connected. 2011 Article Characterization of finite simple semigroup digraphs / J. Meksawang, S. Panma, U. Knauer // Algebra and Discrete Mathematics. — 2011. — Vol. 12, № 1. — С. 53–68. — Бібліогр.: 16 назв. — англ. 1726-3255 2000 Mathematics Subject Classification:05C25, 08B15, 20M19, 20M30 http://dspace.nbuv.gov.ua/handle/123456789/154770 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 characterizes directed graphs which are Cayley graphs of finite simple semigroups, i.e. of a subspecies of completely regular semigroups. Moreover we investigate the structure of Cayley graphs of finite simple semigroups with a one-element connection set. We introduce the conditions for which they are isomorphic and connected. |
| format |
Article |
| author |
Meksawang, J. Panma, S. Knauer, U. |
| spellingShingle |
Meksawang, J. Panma, S. Knauer, U. Characterization of finite simple semigroup digraphs Algebra and Discrete Mathematics |
| author_facet |
Meksawang, J. Panma, S. Knauer, U. |
| author_sort |
Meksawang, J. |
| title |
Characterization of finite simple semigroup digraphs |
| title_short |
Characterization of finite simple semigroup digraphs |
| title_full |
Characterization of finite simple semigroup digraphs |
| title_fullStr |
Characterization of finite simple semigroup digraphs |
| title_full_unstemmed |
Characterization of finite simple semigroup digraphs |
| title_sort |
characterization of finite simple semigroup digraphs |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2011 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/154770 |
| citation_txt |
Characterization of finite simple semigroup digraphs / J. Meksawang, S. Panma, U. Knauer // Algebra and Discrete Mathematics. — 2011. — Vol. 12, № 1. — С. 53–68. — Бібліогр.: 16 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT meksawangj characterizationoffinitesimplesemigroupdigraphs AT panmas characterizationoffinitesimplesemigroupdigraphs AT knaueru characterizationoffinitesimplesemigroupdigraphs |
| first_indexed |
2025-07-14T06:52:46Z |
| last_indexed |
2025-07-14T06:52:46Z |
| _version_ |
1837604240062676992 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 12 (2011). Number 1. pp. 53 – 68
c© Journal “Algebra and Discrete Mathematics”
Characterization of finite simple semigroup
digraphs
J. Meksawang, S. Panma and U.Knauer
Communicated by B. V. Novikov
Abstract. This paper characterizes directed graphs which
are Cayley graphs of finite simple semigroups, i.e. of a subspecies of
completely regular semigroups. Moreover we investigate the struc-
ture of Cayley graphs of finite simple semigroups with a one-element
connection set. We introduce the conditions for which they are
isomorphic and connected.
Introduction
One of the first investigations on Cayley graphs of algebraic structures
can be found in Maschke’s Theorem from 1896 about groups of genus
zero, that is, groups G which possess a generating system A such that
the Cayley graph Cay(G,A) is planar, see for example [15]. In [10] Cay-
ley graphs which represent groupoids, quasigroups, loops or groups are
described. The result for groups originates from [15] and is meanwhile
folklore, see for example [2]. After this it is natural to investigate Cayley
graphs for semigroups which are unions of groups, so-called completely
regular semigroups, see for example [12]. In [1] Cayley graphs which rep-
resent completely regular semigroups which are right (left) groups are
characterized. We now investigate Cayley graphs which represent finite
simple semigroups. Recent studies in different directions investigate tran-
sitivity of Cayley graph of groups and semigroups [7] and of right and left
groups and of Clifford semigroups [11]. Other related results can be found,
2000 Mathematics Subject Classification: 05C25, 08B15, 20M19, 20M30.
Key words and phrases: Cayley graph, digraph, completely regular, completely
simple semigroups, Rees matrix semigroup..
54 Characterization of finite simple semigroup.. .
for example, in [5], [7] and [9]. Relations to network theory together with
many theoretical results are presented in [4]. The concept of Cayley graph
of a groupoid has also been considered in relation to automata theory in
a book by A.V. Kelarev [6].
In this paper , we characterize finite simple semigroup digraphs. We
also describe the structure of Cayley graphs of finite simple semigroup
with a one-element connection set. Moreover we introduce the conditions
for which they are isomorphic and connected.
1. Basic definitions and results
All sets in this paper are assume to be finite. A semigroup S is called simple
if it has no proper ideals. An element a of a semigroup S is completely
regular if there exists an element x ∈ S such that a = axa and ax = xa. A
semigroup S is called completely regular if all its elements are completely
regular. A completely regular semigroup S is called completely simple if it
is simple.
Since all sets in this paper are finite, simple semigroups are completely
simple semigroups. In this case a simple semigroup is always union of
groups.
Suppose that G is a group, I and Λ are nonempty sets, and P is a
Λ× I matrix over a group G.
The Rees matrix semigroup M(G, I,Λ, P ) with sandwich matrix P
consists of all triples (g, i, λ), where i ∈ I, λ ∈ Λ, and g ∈ G with multi-
plication defined by the rule (g1, i1, λ1)(g2, i2, λ2) = (g1pλ1i2g2, i1, λ2).
For an element g of group G we denote by |g| the order of g.
Theorem 1 ([13]). A semigroup S is completely simple if and only if S
is isomorphic to a Rees matrix semigroup.
In the sequel we will mainly use the term Rees matrix semigroup
instead of completely simple semigroup.
For an element of completely simple semigroup S = M(G, I,Λ, P ) we
denote by p1, p2 and p3 the natural projections of S onto G, onto I and
onto Λ, respectively.
Let (V1, E1) and (V2, E2) be digraphs. A mapping ϕ : V1 → V2 is
called a digraph homomorphism if (u, v) ∈ E1 implies (ϕ(u), ϕ(v)) ∈ E2,
i.e. ϕ preserves arcs. We write ϕ : (V1, E1) → (V2, E2). A digraph ho-
momorphism ϕ : (V,E) → (V,E) is called a digraph endomorphism. If
ϕ : (V1, E1) → (V2, E2) is a bijective digraph homomorphism and ϕ−1 is
also a digraph homomorphism, then ϕ is called a digraph isomorphism. A
digraph isomorphism ϕ : (V,E) → (V,E) is calleded a digraph automor-
phism.
J. Meksawang, S. Panma, U. Knauer 55
Let (V1, E1), (V2, E2), . . . , (Vn, En) be digraphs such that Vi ∩ Vj = ∅
for all i 6= j. The disjoint union of (V1, E1), (V2, E2), . . . , (Vn, En) is defined
as ˙⋃n
i=1(Vi, Ei) :=
(
∪̇n
i=1Vi, ∪̇
n
i=1Ei
)
. Let (V,E1), (V,E2), . . . , (V,En)
be digraphs. The edge sum of (V,E1), (V,E2), . . . , (V,En) is defined as
⊕n
i=1(V,Ei) := (V,∪n
i=1En) see for example [10].
Let S be a semigroup (group) and A ⊆ S. We define the Cayley graph
Cay(S,A) as follows: S is the vertex set and (u, v), u, v ∈ S, is an arc in
Cay(S,A) if there exists an element a ∈ A such that v = ua. The set A
is called the connection set of Cay(S,A).
A digraph (V,E) is called a semigroup (group) digraph or digraph of a
semigroup (group) if there exists a semigroup (group) S and a connection
set A ⊆ S such that (V,E) is isomorphic to the Cayley graph Cay(S,A).
For terms in graph theory not defined here see for example [2].
Theorem 2. ([2], [13], [14]) A digraph (V,E) is a Cayley graph of a group
G if and only if Aut(V,E) contains a subgroup ∆ which is isomorphic to
G and for any two vertices u, v ∈ V there exists σ ∈ ∆ such that σ(u) = v.
By the definition of completely simple semigroup, we have the following
lemma.
Lemma 1. Let G be a group, S = M(G, I,Λ, P ) a completely simple
semigroup, A ⊆ S, and let (g1, i1, λ1), (g2, i2, λ2) ∈ S. Then ((g1, i1, λ1),
(g2, i2, λ2)) is an arc in Cay(S,A) if and only if there exists a = (g, l, λ2)
∈ A such that g2 = g1pλ1lg and i1 = i2.
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.
2. Cayley graphs of finite simple semigroups
In view of Lemma 3.2 in [8], we know that a completely simple semigroup
S = M(G, I,Λ, P ) is a right group if and only if |I| = 1.
In [1] Cayley graphs which represent right groups are characterized.
Then we obtain the following proposition.
Proposition 1. Let G be a group, S = M(G, {i},Λ, P ).
Take a = (g, i, β) ∈ S. Then
(1) the Cayley graph Cay(S, {a}) contains a strong group subdigraph
Cay(G, {pβig});
(2) ((g1, i, λ1), (g2, i, λ2)) is an arc in Cay(S, {a}) if and only if g2 =
g1pλ1ig and λ2 = β.
56 Characterization of finite simple semigroup.. .
If S = M(G, I,Λ, P ) is a completely simple semigroup, let pi denote
the projection of S on to its ith coordinate. In the next theorem, we
characterize a Cayley graph of a finite simple semigroup.
Theorem 3. A digraph (V,E) is a Cayley graph of a finite simple semi-
group if and only if the following conditions hold
(1) (V,E) is the disjoint union of n isomorphic subdigraphs
(V1, E1), (V2, E2), ..., (Vn, En) for some n ∈ N;
(2) (Vi, Ei) has n subdigraphs (Vi1, Ei1), (Vi2, Ei2), ..., (Vin, Ein) such
that (Vi, Ei) =
⊕n
j=1(Vij , Eij) with Vi = Vij
for every j ∈ {1, 2, .., n};
(3) (Vij , Eij) contains m disjoint strong subdigraphs (V 1
ij , E
1
ij), (V
2
ij , E
2
ij)
, ..., (V m
ij , E
m
ij ) such that Vij =
⋃m
α=1 V
α
ij ;
(4) there exists a group G and a family of digraph isomorphisms
{fα
ij}
m
α=1 such that fα
ij : (V
α
ij , E
α
ij) → Cay(G, aαijA
α
ij) for some aαij ∈
G, Aα
ij ⊆ G with Aα
kj = Aα
tj , aαkj = aαtj for all k, t ∈ {1, 2, ..., n};
(5) for each u ∈ V α
ij , v ∈ V β
ij , (u, v) ∈ E if and only if fβ
ij(v) = fα
ij(u)a
α
ija
for some a ∈ Aβ
ij .
Proof. (⇒) Let (V,E) be a Cayley graph of a finite simple semigroup.
Then there exists a finite simple semigroup S = M(G, I,Λ, P ) where G is
a group, I = {1, 2, ..., n}, Λ = {1, 2, ...,m}, and P is a Λ× I matrix over
a group G, such that (V,E) ∼= Cay(S,A) for some A ⊆ S. Hence we will
prove that (1), (2), (3), (4) and (5) are true for Cay(S,A).
(1) For each i ∈ I, set Vi := G × {i} × Λ, and Ei := E(Cay(S,A)) ∩
(Vi × Vi). Hence (Vi, Ei) is a strong subdigraph of Cay(S,A) and
Cay(S,A) =
⋃n
i=1(Vi, Ei). We show that (V1, E1), (V2, E2), . . . ,
(Vn, En) are isomorphic. Let p, q ∈ I, p 6= q, define a map φ from
(Vp, Ep) to (Vq, Eq) by φ((g, p, r)) = (g, q, r). Since |Vp| = |Vq|, φ is a
well defined bijection. To prove that φ and φ−1 are digraph homomor-
phisms. For (g, p, r), (g′, p, r′) ∈ Vp, take ((g, p, r), (g′, p, r′)) ∈ Ep.
Since Ep ⊆ E(Cay(S,A)), ((g, p, r), (g′, p, r′)) is an arc in Cay(S,A).
By Lemma 1, there exists (a, l, r′′) ∈ A such that g′ = gprla,
r′ = r′′, and thus (g′, q, r′) = (gprla, q, r
′′) = (g, q, r) (a, l, r′′).
Then ((g, q, r), (g′, q, r′)) is an arc in Cay(S,A). It follows that
((g, q, r), (g′, q, r′)) ∈ Eq. This shows that φ is a digraph homo-
morphism. Similarly, φ−1 is a digraph homomorphism. Hence φ is
a digraph isomorphism. Now we prove that Cay(S,A) is the dis-
joint union of (V1, E1), (V2, E2), . . . , (Vn, En). By definition of Vi,
J. Meksawang, S. Panma, U. Knauer 57
S = ˙⋃Vi. Since Ei ⊆ E
(
Cay(S,A)
)
, ˙⋃Ei ⊆ E
(
Cay(S,A)
)
. Let
(
(g, j, r), (ǵ, k, ŕ)
)
∈ E(Cay(S,A). By Lemma 1, j = k, and thus
(
(g, j, r), (ǵ, k, ŕ)
)
∈ Ek. Then
(
(g, j, r), (ǵ, k, ŕ)
)
∈ ˙⋃Ei. Hence
E
(
Cay(S,A)
)
⊆ ˙⋃Ei, and so E
(
Cay(S,A)
)
= ˙⋃Ei. Therefore
Cay(S,A) = ˙⋃(Vi, Ei).
(2) Let Sij = M(G, {i},Λ, Pj) where i, j ∈ {1, 2, .., n},
Pj =
p1j
p2j
.
.
.
pmj
,
and Pj is the jth column of P , and let Aij =: {(g, i, β)|(g, j, β) ∈ A}.
Take (Vij , Eij) =: Cay(Sij , Aij). Hence Vij = M(G, {i},Λ, Pj) = Vi.
To prove that (Vi, Ei) =
⊕n
j=1(Vij , Eij). Let ((g, i, α), (g′, i, β)) ∈ Ei.
Therefore ((g, i, α), (g′, i, β)) is an arc in Cay(S,A). By Lemma 1,
there exists (g′′, l, γ) ∈ A such that γ = β and g′ = gpαlg
′′. Since
(g′′, l, β) ∈ A, (g′′, i, β) ∈ Ail. Thus ((g, i, α), (g′, i, β)) is an arc in
Cay(Sil, Ail) as (g, i, α)(g′′, i, β) = (gpαlg
′′, i, β) = (g′, i, β). There-
fore ((g, i, α) , (g′, i, β)) ∈ Eil ⊆
⋃n
j=1Eij , and so Ei ⊆
⋃n
j=1Eij . Let
((g, i, α), (g′, i, β)) ∈
⋃n
j=1Eij . Therefore ((g, i, α), (g′, i, β)) ∈ Eil
for some l ∈ {1, 2, .., n}. It follows that ((g, i, α), (g′, i, β)) is an
arc in Cay(Sil, Ail). Then there exists (g′′, i, γ) ∈ Ail such that
γ = β and g′ = gpαlg
′′ by Lemma 1. Hence (g′′, l, β) ∈ A because
(g′′, i, β) ∈ Ail. Then (g′, i, β) = (gpαlg
′′, i, β) = (g, i, α)(g′′, l, β),
((g, i, α), (g′, i, β)) is an arc in Cay(S,A). Therefore ((g, i, α),
(g′, i, β)) ∈ Ei, and thus
⋃n
j=1Eij ⊆ Ei. Hence Ei =
⋃n
j=1Eij .
This show that (Vi, Ei) =
⊕n
j=1(Vij , Eij).
(3) Set V α
ij := M(G, {i}, {α}, Pα
j ), E
α
ij := E(Cay(Sij , Aij))∩(V α
ij ×V α
ij )
where Pα
j = [pαj ] is an 1× 1 matrix. Therefore V α
ij ⊆ Vij and thus
(V α
ij , E
α
ij) is a strong subdigraph of (Vij , Eij). Let α, β ∈ Λ and
α 6= β. To prove that (V α
ij , E
α
ij) and (V β
ij , E
β
ij) are disjoint. Since
V α
ij ∩V
β
ij = ∅, by the definition of Eα
ij and Eβ
ij ,E
α
ij∩E
β
ij = ∅. Therefore
(V α
ij , E
α
ij) and (V β
ij , E
β
ij) are disjoint subdigraphs of (Vij , Eij). Hence
⋃m
α=1 V
α
ij =
⋃m
α=1M(G, {i}, {α}, [pαj ]) = M(G, {i},Λ, Pj) = Vi.
(4) Let Aα
ij := {g|(g, i, α) ∈ Aij}. To prove that (V α
ij , E
α
ij)
∼=
Cay(G, aαijA
α
ij) where aαij = pαj . Let fα
ij : (V α
ij , E
α
ij) →
58 Characterization of finite simple semigroup.. .
Cay(G, pαjA
α
ij) be the projection of V α
ij on to its first coordinate,
i.e. fα
ij = p1. We first show that fα
ij and fα
ij
−1 are digraph homo-
morphisms. For (g, i, α), (g′, i, α) ∈ V α
ij , take ((g, i, α), (g′, i, α)) ∈
Eα
ij . By the definition of Eα
ij , ((g, i, α), (g′, i, α)) is an arc in
Cay(Sij , Aij). Then there exists (g′′, i, γ) ∈ Aij such that g′ =
gpαjg
′′ and α = γ by Lemma 1. Thus there is g′′ ∈ Aα
ij . It follows
that (fα
ij(g, i, α), f
α
ij(g
′, i, α)) = (g, g′) is an arc in Cay(G, pαjA
α
ij).
Hence fα
ij is a digraph homomorphism. For g, g′ ∈ G, let (g, g′) be
an arc in Cay(G, pαjA
α
ij). Therefore g′ = gpαjg
′′ for some g′′ ∈ Aα
ij .
By the definition of Aα
ij , there is (g′′, i, α) ∈ Aij and so (g′, i, α) =
(gpαjg
′′, i, α) = (g, i, α)(g′′, i, α). Therefore ((g, i, α), (g′, i, α)) is an
arc in Cay(Sij , Aij). This shows that fα
ij
−1 is a digraph homo-
morphism. Let k, t ∈ {1, 2, ..., n}. We show that Aα
kj = Aα
tj . Take
g ∈ Aα
kj . Then (g, k, α) ∈ Akj and (g, j, α) ∈ A. By the definition of
Atj , (g, t, α) ∈ Atj , and thus g ∈ Aα
tj . This shows that Aα
kj ⊆ Aα
tj .
Similarly Aα
kj ⊇ Aα
tj . Thus Aα
kj = Aα
tj for all k, t ∈ {1, 2, ..., n}. Since
aαkj = pαj and aαtj = pαj , a
α
kj = aαtj for all k, t ∈ {1, 2, ..., n}.
(5) For each u = (g, i, α) ∈ V α
ij , and v = (g′, i, β) ∈ V β
ij . We prove that
((g, i, α), (g′, i, β)) ∈ E if and only if fβ
ij(v) = fα
ij(u)a
α
ija for some
a ∈ Aβ
ij .
(⇒) Let ((g, i, α), (g′, i, β)) ∈ E. Then ((g, i, α), (g′, i, β)) is an arc
in Cay(S,A). By Lemma 1, there exists (a, j, ξ) ∈ A such that
g′ = gpαja and β = ξ. Then we have that (a, j, β) = (a, j, ξ) ∈ A.
By the definition of Aij , there exists (a, i, β) ∈ Aij , and hence a ∈ Aβ
ij .
Therefore fβ
ij(v) = g′ = gpαja = fα
ij(u)a
α
ija where aαij = pαj .
(⇐) Let fβ
ij(v) = fα
ij(u)a
α
ija for some a ∈ Aβ
ij . Therefore g′ =
fβ
ij(v) = fα
ij(u)a
α
ija = gaαija and there exists (a, i, β) ∈ Aij . By the
definition of Aij , there is (a, j, β) ∈ A. Since aαij = pαj , (g
′, i, β) =
(gaαija, i, β) = (gpαja, i, β) = (g, i, α)(a, j, β), and thus
((g, i, α), (g′, i, β)) is an arc in Cay(S,A).
(⇐) Choose k ∈ {1, 2, ..., n}, by (1), (2), and (3), we get V =
⋃n
i=1
⋃m
α=1 V
α
ik
is the disjoint union. Let S = M(G, I,Λ, P ) where I = {1, 2, ..., n},
Λ = {1, 2, ...,m},
P =
a1k1 a1k2 · · · a1kn
a2k1 a2k2 · · · a2kn
. . . . . . . . . . . . . . . . . . .
amk1 amk2 · · · amkn
,
and let A :=
⋃m
α=1
⋃n
j=1(A
α
jk × {k} × {α}). We show that (V,E) ∼=
J. Meksawang, S. Panma, U. Knauer 59
Cay(S,A). Define a map f from (V,E) to Cay(S,A) by f(v) = (fα
ik(v), i, α)
for any v ∈ V α
ik , i ∈ {1, 2, ..., n}, and α ∈ {1, 2, ...,m}. Let u, v ∈ V and
u = v. Then u = v ∈ V β
rk for some r ∈ {1, 2, ..., n} and β ∈ {1, 2, ...,m}.
Hence fβ
rk(u) = fβ
rk(v) and (fβ
rk(u), r, β) = (fβ
rk(v), r, β). Therefore f is
well defined. Let u, v ∈ V and f(u) = f(v). Then u ∈ V β
lk and v ∈ V δ
tk
for some l, t ∈ {1, 2, ..., n} and β, δ ∈ {1, 2, ...,m}, and so (fβ
lk(u), l, β) =
f(u) = f(v) = (f δ
tk(v), t, δ). Hence fβ
lk(u) = f δ
tk(v), l = t, and β = δ.
Then u, v ∈ V β
lk and fβ
lk(u) = fβ
lk(v). Since fβ
lk is an isomorphism, u = v.
This shows that f is an injection. By (4), |G× {i} × {α}| = |G| = |V α
ik |
for all i ∈ {1, 2, ..., n} and α ∈ {1, 2, ...,m}. Thus |S = M(G, I,Λ, P )| =
|
⋃n
i=1
⋃m
α=1(G× {i} × {α})| = |
⋃n
i=1
⋃m
α=1 V
α
ik | = |V |. Hence f is a sur-
jection. Now we must prove that f and f−1 are digraph homomorphisms.
Let u, v ∈ V and (u, v) ∈ E. By (1), u, v ∈ Vt for some t ∈ {1, 2, ..., n}.
Then u ∈ V β
tk and v ∈ V δ
tk for some β, δ ∈ {1, 2, ...,m}. From (5), f δ
tk(v) =
fβ
tk(u)a
β
tka for some a ∈ Aδ
tk. Hence (a, k, δ) ∈ (Aδ
tk × {k} × {δ}) ⊆ A. By
(4), aβtk = aβkk. Since aβkk is the entry in the βth row and kht column of
P , aβtk = aβkk = pβk. Therefore f(v) = (f δ
tk(v), t, δ) = (fβ
tk(u)a
β
tka, t, δ) =
(fβ
tk(u)pβka, t, δ) = (fβ
tk(u), t, β)(a, k, δ) = f(u)(a, k, δ). Then we get that
(f(u), f(v)) is an arc in Cay((G×Ln×Rm), A). This shows that f is a di-
graph homomorphism. Let g, g′ ∈ G, j, t ∈ {1, 2, ..., n}, β, δ ∈ {1, 2, ...,m},
and let ((g, j, β), (g′, t, δ)) be an arc in Cay(S,A). Then there exists
(a, k, ξ) ∈ A such that g′ = gpβka, t = j, and δ = ξ. By the definition of A,
a ∈ Aξ
qk = Aδ
qk for some q ∈ {1, 2, ..., n}. From (4), Aδ
qk = Aδ
jk and so a ∈
Aδ
jk Since g, g′ ∈ G, there exists u ∈ V β
jk and v ∈ V δ
jk such that fβ
jk(u) = g
and f δ
jk(v) = g′ by (4). Therefore f δ
jk(v) = fβ
jk(u)pβka. By the definition
of P and (4), pβk = aβkk = aβjk. Hence (f−1(g, lj , rβ), f
−1(g′, lt, rδ)) =
(f−1((fβ
jk(u), j, β)), f
−1((f δ
jk(v), j, δ))) = (u, v) ∈ E by (5). Thus f−1 is a
digraph homomorphism.
Example 1. Consider the finite simple semigroup S = M(Z3, I,Λ,
P ),Z3 = {0̄, 1̄, 2̄} with I = {1, 2}, Λ = {1, 2},
P =
[
0̄ 0̄
0̄ 1̄
]
, and thus P1 =
[
0̄
0̄
]
, P2 =
[
0̄
1̄
]
,
and let a1 = (0̄, 1, 1), a2 = (1̄, 2, 1), a3 = (0̄, 2, 2). Then we give the Cayley
graphs Cay(S,A) for all the three different one-element connection sets
A, as indicated in the pictures.
60 Characterization of finite simple semigroup.. .
s s s s s s
s s s s s s
0̄11 1̄11 2̄11 0̄21 1̄21 2̄21
0̄12 1̄12 2̄12 0̄22 1̄22 2̄22
✡✠
✁✁✕ ❆❆
✡✠
✁✁✕ ❆❆
✡✠
✁✁✕ ❆❆
✡✠
✁✁✕ ❆❆
✡✠
✁✁✕ ❆❆
✡✠
✁✁✕ ❆❆✻ ✻ ✻ ✻ ✻ ✻
Fig. 1. Cay(S, {a1})
s s s s s s
s s s s s s
0̄11 1̄11 2̄11 0̄21 1̄21 2̄21
0̄12 1̄12 2̄12 0̄22 1̄22 2̄22
✟✟✟✟✟✟✟✟✟✟✯
❅
❅
❅
❅
❅■
❅
❅
❅
❅
❅■
✟✟✟✟✟✟✟✟✟✟✯
❅
❅
❅
❅
❅■
❅
❅
❅
❅
❅■
✲ ✲ ✲ ✲
✡ ✠✻ ✡ ✠✻
Fig. 2. Cay(S, {a2})
s s s s s s
s s s s s s
0̄11 1̄11 2̄11 0̄21 1̄21 2̄21
0̄12 1̄12 2̄12 0̄22 1̄22 2̄22
Fig. 3. Cay(S, {a3})
❄ ❄ ❄ ❄ ❄ ❄✲ ✲ ✲ ✲
☛ ✟
❄
☛ ✟
❄
So we have
Cay(S, {a1}) =
Cay(M(Z3, {1},Λ, P1), {(0̄, 1, 1)})
⋃
Cay(M(Z3, {2},Λ, P1), {(0̄, 2, 1)}),
Cay(S, {a2}) =
Cay(M(Z3, {1},Λ, P2), {(1̄, 1, 1)})
⋃
Cay(M(Z3, {2},Λ, P2), {(1̄, 2, 1)}),
Cay(S, {a3}) =
Cay(M(Z3, {1},Λ, P2), {(0̄, 1, 2)})
⋃
Cay(M(Z3, {2},Λ, P2), {(0̄, 2, 2)}).
Therefore Cay(S, {a1, a2, a3}) =
[
Cay(M(Z3, {1},Λ, P1), {(0̄, 1, 1)})
⊕
Cay(M(Z3, {1},Λ, P2),
{(1̄, 1, 1), (0̄, 1, 2)})
]
⋃
[
Cay(M(Z3, {2},Λ, P1), {(0̄, 2, 1)})
⊕
Cay(M(Z3, {2},Λ, P2),
{(1̄, 2, 1), (0̄, 2, 2)})
]
.
We see that Cay(S, {a1, a2, a3}) = (V1, E1)
⋃
(V2, E2) where
(V1, E1) =
[
Cay(M(Z3, {1},Λ, P1), {(0̄, 1, 1)})
J. Meksawang, S. Panma, U. Knauer 61
⊕
Cay(M(Z3, {1},Λ, P2), {(1̄, 1, 1), (0̄, 1, 2)})
]
and
(V2, E2) =
[
Cay(M(Z3, {2},Λ, P1), {(0̄, 2, 1)})
⊕
Cay(M(Z3, {2},Λ, P2), {(1̄, 2, 1), (0̄, 2, 2)})
]
.
Let (V11, E11) = Cay(M(Z3, {1},Λ, P1), {(0̄, 1, 1)}),
(V12, E12) = Cay(M(Z3, {1},Λ, P2), {(1̄, 1, 1), (0̄, 1, 2)}),
(V21, E21) = Cay(M(Z3, {2},Λ, P1), {(0̄, 2, 1)}),
and (V22, E22) = Cay(M(Z3, {2},Λ, P2), {(1̄, 2, 1), (0̄, 2, 2)}).
Then we get that (V11, E11), (V12, E12), (V21, E21) and (V12, E12) are right
group digraphs, and so (V1, E1) = (V11, E11)
⊕
(V12, E12)
and (V2, E2) = (V21, E21)
⊕
(V12, E12).
In the next lemmas, we describe the structure of Cayley graphs of a
completely simple semigroup with a one-element connection set, which
will be used in Theorem 4 and Theorem 5. By the proof of Theorem 3
(1-2), we have the following lemma.
Lemma 2. Let S = M(G, I,Λ, P ) be a finite simple semigroup, I =
{1, 2, . . . , n}, Λ = {1, 2, . . . ,m}, a = (g, j, β) ∈ S, Pi the ith column
of P. Then Cay(S, {a}) is the disjoint union of n isomorphic strong
subdigraphs Cay(S1, {(g, 1, β)}), Cay(S2, {(g, 2, β)}), . . .,
Cay(Sn, {(g, n, β)}) where Si = M(G, {i},Λ, Pj).
Lemma 3. Let S = M(G, I,Λ, P ) be a finite simple semigroup,
I = {1, 2, . . . , n}, Λ = {1, 2, . . . ,m}, G/〈pβjg〉 = {g1〈pβjg〉, g2〈pβjg〉, . . . ,
gt〈pβjg〉} the set of all distinct left cosets of 〈pβjg〉 in G, a = (g, j, β) ∈ S
and let Mik =
(
gk〈pβjg〉 × {i} × {β}
)
∪
(
⋃
α 6=β(gk〈pβjg〉 g
−1p−1
αj × {i} ×
{α})
)
, where k ∈ {1, 2, . . . , t} and i ∈ I. Then Mi1,Mi2, . . . ,Mit are
disjoint.
Proof. Since {g1〈pβjg〉, g2〈pβjg〉, . . . , gt〈pβjg〉} is the set of all distinct left
cosets of 〈pβjg〉 in G, we get that Mi1,Mi2, . . . ,Mit are disjoint.
Lemma 4. Let S = M(G, I,Λ, P ) be a finite simple semigroup, I =
{1, 2, . . . , n}, Λ = {1, 2, . . . ,m}, a = (g, j, β) ∈ S, (Mik, Eik) a strong
subdigraph of Cay(S, {a}). Then (Mik1 , Eik1)
∼= (Mik2 , Eik2) for all
k1, k2 ∈ {1, 2, . . . , t}.
Proof. We define f : (Mik1 , Eik1) → (Mik2 , Eik2) by
(
gk1(pβjg)
r, i, β
)
7→
(
gk2(pβjg)
r, i, β
)
(
gk1(pβjg)
rg−1p−1
αj , i, α
)
7→
(
gk2(pβjg)
rg−1p−1
αj , i, α
)
forα 6= β.
Since, for all k ∈ {1, 2, . . . , t}, gk〈pβjg〉 = {gk(pβjg), gk(pβjg)
2, . . . ,
gk(pβjg)
|pβjg|}, f is a well defined bijection. Since we define the Cayley
graph with right action, f and f−1 are homomorphisms. This means that
f is a digraph isomorphism. Hence (Mik1 , Eik1)
∼= (Mik2 , Eik2).
62 Characterization of finite simple semigroup.. .
Lemma 5. Let S = M(G, I,Λ, P ) be a finite simple semigroup,
I = {1, 2, . . . , n}, Λ = {1, 2, . . . ,m}, a = (g, j, β) ∈ S. Then
Cay(Si, {(g, i, β)}) = ˙⋃t
k=1(Mik, Eik).
Proof. We first show that Si = ˙⋃t
k=1Mik. Since Mik ⊆ Si for all k ∈
{1, 2, ..., t} , ˙⋃t
k=1Mik ⊆ Si. We will show that Si ⊆ ˙⋃t
k=1Mik. Let x =
(g
′
, i, λ) ∈ Si, we get g
′
∈ G =
⋃t
k=1 gk〈pβjg〉, and thus g
′
= gw(pβjg)
v
for some v ∈ N and w ∈ {1, 2, . . . , t}. We need to consider the following
two cases.
(case 1) If λ = β, then x =
(
gw(pβjg)
v, i, β
)
∈
(
gw〈pβjg〉×{i}×{β}
)
⊆
Miw ⊆ ˙⋃t
k=1Mik.
(case 2) If λ 6= β, then xa =
(
gw(pβjg)
v, i, λ
)
(g, j, β) =
(
gw(pβjg)
v
pλjg, i, β
)
. Since gw(pβjg)
vpλjg ∈ G =
⋃t
k=1 gk〈pβjg〉,
gw(pβjg)
vpλjg ∈ gu〈pβjg〉 for some u ∈ {1, 2, . . . , t}, we get
that gw(pβjg)
vpλjg = gu(pβjg)
v
′
for some v́ ∈ N, and thus
gw(pβjg)
v = gu(pβjg)
v
′
g−1p−1
λj . Therefore x =
(
gw(pβjg)
v,
i, λ
)
=
(
gu(pβjg)
dg−1p−1
λj , i, λ
)
∈
(
gu〈pβjg〉g
−1p−1
λj × {i} ×
{λ}
)
⊆ Miu ⊆ ˙⋃t
k=1Mik.
Hence Si ⊆ ˙⋃t
k=1Mik. Then we conclude that Si = ˙⋃t
k=1Mik.
Since (Mi1, Ei1), (Mi2, Ei2), . . . , (Mit, Eit) are strong subdigraphs of
Cay(Si, {(g, i, β)}) , E
( ˙⋃t
k=1(Mik, Eik)
)
⊆ E
(
Cay(Si, {(g, i, β)})
)
. Let
x = (u1, i, λ1) , y = (u2, i, λ2) ∈ Si and (x, y) be an arc in
Cay(Si, {(g, i, β)}). Therefore u2 = u1pλ1jg and λ2 = β by Proposi-
tion 1(2). Since Si = ˙⋃t
k=1Mik, x ∈ Mib1 and y ∈ Mib2 for some
b1, b2 ∈ {1, 2, . . . , t}. Hence y ∈
(
gb2〈pβjg〉 × {i} × {β}
)
, and thus y =
(gb2(pβjg)
d
′
, i, β) for some d
′
∈ {1, 2, . . . , |pβj |}. Then u2 = gb2(pβjg)
d
′
.
We need only consider two cases:
(case1) If λ1 6= β, then x ∈
(
gb1〈pβjg〉g
−1p−1
λ1j
× {i} × {λ1}
)
. Hence
x =
(
gb1(pβjg)
cg−1p−1
λ1j
, i, λ1
)
for some c ∈ {1, 2, ..., |pβjg|},
and thus u1 = gb1(pβjg)
cg−1p−1
λ1j
. Since u2 = u1pλ1jg,
gb2(pβjg)
d
′
= gb1(pβjg)
cg−1p−1
λ1j
pλ1jg
= gb1(pβjg)
c.
Then b1 = b2, and thus x, y ∈ Mib1 . Hence (x, y) ∈ Eib1 . We
get that (x, y) is an arc in ˙⋃t
k=1(Mik, Eik).
J. Meksawang, S. Panma, U. Knauer 63
(case2) If λ1 = β, then x ∈
(
gb1〈pβjg〉 × {i} × {β}
)
. Hence
x =
(
gb1(pβjg)
c
′
, i, β
)
for some c
′
∈ {1, 2, ..., |pβjg|}, and so
u1 = gb1(pβjg)
c
′
. Since u2 = u1pλ1jg,
gb2(pβjg)
d
′
= gb1(pβjg)
c
′
pλ1jg
= gb1(pβjg)
c
′
pβjg
= gb1(pβjg)
c
′
pβjg
= gb1(pβjg)
c
′
+1.
Therefore b1 = b2 and thus x, y ∈ Mib1 . Hence (x, y) ∈ Eib1 .
We get that (x, y) is an arc in ˙⋃t
k=1(Mik, Eik).
Hence E
( ˙⋃t
k=1(Mik, Eik)
)
= E(Cay(Si, {(g, i, β)})). We conclude
that Cay(Si, {(g, i, β)}) = ˙⋃t
k=1(Mik, Eik).
Lemma 6. Let S = M(G, I,Λ, P ) be a finite simple semigroup, I =
{1, 2, . . . , n}, Λ = {1, 2, . . . ,m}, a = (g, j, β) ∈ S. Then (Mik, Eik) ∼=
Cay
(
〈pβjg〉 × Rm, {(pβjg, rβ)}
)
where Rm = {r1, r2, . . . , rm} is a right
zero semigroup.
Proof. We define f : (Mik, Eik) → Cay
(
〈pβjg〉 ×Rm, {(pβjg, rβ)}
)
by
(
gk(pβjg)
q, i, β
)
7→
(
gk(pβjg)
q, rβ
)
(
gk(pβjg)
qg−1p−1
αj , i, α
)
7→
(
gk(pβjg)
q−1, rα
)
forα 6= β.
Clearly, f is a well defined bijection.
We will show that f and f−1 are digraph homomorphisms. For x, y ∈
Mik, let (x, y) ∈ Eik. Then (x, y) is an arc in Cay(S, {a}), and thus
y = xa. By Proposition 1(2), p3(y) = β. Hence y ∈ (gk〈pβjg〉×{i}×{β}),
and so y = (gk(pβjg)
c, i, β) for some c ∈ {1, 2, . . . , |pβjg|}. We need only
consider two cases :
(case 1) If x ∈ (gk〈pβjg〉 × {i} × {β}), then x =
(
gk(pβjg)
d, i, β
)
for
some d ∈ {1, 2, . . . , |pβjg|}. Since y = xa,
(
gk(pβjg)
c, i, β
)
=
(
gk(pβjg)
d, i, β
)
(g, j, β) =
(
gk(pβjg)
dpβjg, i, β
)
.
Thus gk(pβjg)
c = gk(pβjg)
dpβjg, and so
f(y) = f
(
gk(pβjg)
c, i, β
)
=
(
gk(pβjg)
c, rβ
)
=
(
gk(pβjg)
dpβjg, rβ
)
64 Characterization of finite simple semigroup.. .
=
(
gk(pβjg)
d, rβ
)(
pβjg, rβ
)
= f(x)(pβjg, rβ).
Therefore
(
f(x), f(y)
)
is an arc in Cay
(
〈pβjg〉 ×Rm,
{(pβjg, rβ)}
)
.
(case 2) If x ∈
(
⋃
α 6=β(gk〈pβjg〉g
−1p−1
αj × {i} × {α})
)
, then x =
(gk(pβjg)
d
′
g−1p−1
αj , i, α
)
for some α 6= β and d
′
∈ {1, 2, . . . ,
|pβjg|}. Since y = xa,
(
gk(pβjg)
c, i, β
)
=
(
gk(pβjg)
d
′
g−1p−1
αj , i, α
)
(g, j, β)
=
(
gk(pβjg)
d
′
g−1p−1
αj pαjg, i, β
)
=
(
gk(pβjg)
d
′
, i, β
)
.
Thus gk(pβjg)
c = gk(pβjg)
d
′
, and so
f(y) =
(
gk(pβjg)
c, rβ
)
=
(
gk(pβjg)
d
′
, rβ
)
=
(
gk(pβjg)
d
′
−1pβjg, rβ
)
=
(
gk(pβjg)
d
′
−1, rα
)
(pβjg, rβ)
= f(x)(pβjg, rβ).
Therefore
(
f(x), fy)
)
is an arc in Cay
(
〈pβjg〉 ×Rm,
{(pβjg, rβ)}
)
.
This means that f is a digraph homomorphism. Similarly, f−1 is a digraph
homomorphism.
Hence (Mik, Eik) ∼= Cay
(
〈pβjg〉 ×Rm, {(pβjg, rβ)}
)
.
Example 2. Consider the finite simple semigroup S = M(Z2 × Z2,
I,Λ, P ),Z2 × Z2 = {0̄0̄, 0̄1̄, 1̄0̄, 1̄1̄} with I = {1, 2}, Λ = {1, 2},
P =
[
0̄0̄ 1̄0̄
0̄1̄ 1̄1̄
]
, and thus P1 =
[
0̄0̄
0̄1̄
]
, P2 =
[
1̄0̄
1̄1̄
]
.
Then we give the Cayley graph Cay
(
S, {(1̄0̄, 1, 2)}
)
J. Meksawang, S. Panma, U. Knauer 65
s s
s s
s s
s s
s s
s s
s s
s s
0̄0̄11 0̄0̄12
0̄1̄11 0̄1̄12
1̄0̄11 1̄0̄12
1̄1̄11 1̄1̄12
0̄0̄21 0̄0̄22
0̄1̄21 0̄1̄22
1̄0̄21 1̄0̄22
1̄1̄21 1̄1̄22
❆
❆
❆
❆
❆
❆
❆
❆
❆
❆❯
❆
❆
❆
❆
❆
❆
❆
❆
❆
❆❯
✁
✁
✁
✁
✁
✁
✁
✁
✁
✁✕
✁
✁
✁
✁
✁
✁
✁
✁
✁
✁✕
✟
✠
✛
✛
�
✁
✛
✛
❆
❆
❆
❆
❆
❆
❆
❆
❆
❆❯
❆
❆
❆
❆
❆
❆
❆
❆
❆
❆❯
✁
✁
✁
✁
✁
✁
✁
✁
✁
✁✕
✁
✁
✁
✁
✁
✁
✁
✁
✁
✁✕
✟
✠
✛
✛
�
✁
✛
✛
Fig. 4. Cay
(
S, {(1̄0̄, 1, 2)}
)
In Fig. 4, we see that Cay
(
S, {(1̄0̄, 1, 2)}
)
= Cay(S1, {(1̄0̄, 1, 2)})
˙⋃Cay(S2, {(1̄0̄, 2, 2)}) where S1 = M(Z2×Z2, {1},Λ, P1), S2 = M(Z2×
Z2, {2},Λ, P2). Then it is the union of right group digraphs.
We have 〈p211̄0̄〉 = {1̄1̄, 0̄0̄},Z2×Z2/〈p211̄0̄〉 = {g1〈p211̄0̄〉, g2〈p211̄0̄〉}
where g1 = 0̄0̄, g2 = 0̄1̄. Hence
M11 = {(1̄1̄, 1, 2), (0̄0̄, 1, 2), (0̄1̄, 1, 1), (1̄0̄, 1, 1)},
M12 = {(1̄0̄, 1, 2), (0̄1̄, 1, 2), (0̄0̄, 1, 1), (1̄1̄, 1, 1)},
M21 = {(1̄1̄, 2, 2), (0̄0̄, 2, 2), (0̄1̄, 2, 1), (1̄0̄, 2, 1)},
M22 = {(0̄1̄, 2, 2), (1̄0̄, 2, 2), (0̄0̄, 2, 1), (1̄1̄, 2, 1)}.
We see that (M11, E11) ∼= (M12, E12) ∼= (M21, E21) ∼= (M22, E22) ∼=
Cay
(
〈p211̄0̄〉×R2, {(p211̄0̄, r2)}
)
and Cay
(
S, {a}
)
= ˙⋃2
i=1
˙⋃2
k=1(Mik, Eik)
where R2 = {r1, r2} is a right zero semigroup.
By Lemma 2-6, we get that a Cayley graph of a finite simple semi-
group M(G, I,Λ, P ) with a one-element connection set {(g, j, β)}, is the
disjoint union of |I|t copies of Cay
(
〈pβjg〉 × R|Λ|, {(pβjg, rβ)}
)
where
t = |G/〈pβjg〉|. Then |I|t is the number of connected components of
Cay(S, {a}).
In the next theorem, we give the conditions for two Cayley graphs of
finite simple semigroups Cay(S, {a}) and Cay(S, {b}) to be isomorphic.
Theorem 4. Let S = M(G, I,Λ, P ) be a finite simple semigroup, I =
{1, 2, . . . , n}, Λ = {1, 2, . . . ,m},a = (g, j, β), b = (g
′
, i, λ) ∈ S. Then
Cay(S, {a}) ∼= Cay(S, {b}) if and only if |pβjg| = |pλig
′
|.
Proof. (=⇒) Suppose that Cay(S, {a}) ∼= Cay(S, {b}). By Lemma 6, we
get that Cay
(
〈pβjg〉 ×Rm, {(pβjg, rβ)}
)
∼=
66 Characterization of finite simple semigroup.. .
Cay
(
〈pλig
′
〉×Rm, {(pλig
′
, rλ)}
)
. Therefore |〈pβjg〉×Rm| = |〈pλig
′
〉×Rm|,
and thus |〈pβjg〉| = |〈pλig
′
〉|. Hence |pβjg| = |pλig
′
|.
(⇐=) Assume that |pβjg| = |pλig
′
| = l.
By Lemma 2-6, we only need to show that
Cay
(
〈pβjg〉×Rm, {(pβjg, rβ)}
)
∼= Cay
(
〈pλig
′
〉×Rm, {(pλig
′
, rλ)}
)
where
Rm = {r1, r2, . . . , rm} is a right zero semigroup. We define
f : Cay
(
〈pβjg〉 ×Rm, {(pβjg, rβ)}
)
→ Cay
(
〈pλig
′
〉 ×Rm, {(pλig
′
, rλ)}
)
by f
(
(pβjg)
r, rµ
)
=
(
(pλig
′
)r, rλ
)
ifµ = β
(
(pλig
′
)r, rβ
)
ifµ = λ
(
(pλig
′
)r, rα
)
otherwise
Since |pβjg| = |pλig
′
|, f is an isomorphism.
Now we give the conditions for a Cayley graph of a finite simple
semigroup with a one-element connection set to be connected.
Theorem 5. Let S = M(G, I,Λ, P ) be a finite simple semigroup, a =
(g, j, β) ∈ S. Then Cay(S, {a}) is connected if and only if G = 〈pβjg〉 and
|I| = 1, in particular this means that S is a right group.
Proof. (⇒) Let Cay(S, {a}) is connected. By Lemma 2, we get |I| = 1
and G = 〈pβjg〉.
(⇐) Assume that G = 〈pβjg〉 and |I| = 1. We will prove that
Cay(S, {a}) is connected. Let (g1, i, λ1), (g2, i, λ2) ∈ S. Hence g1, g2 ∈
〈pβjg〉. Therefore g1 = (pβjg)
r and g2 = (pβjg)
q for some r, q ∈ {1, 2, ...,
|pβjg|}. Then r ≤ q or r > q.
(case 1) For λ1 = λ2 = β. If r ≤ q, then q = r + t for some t ∈ N ∪ {0}.
Then we get (g1, i, λ1) =
(
(pβjg)
r, i, β
)
,
(
(pβjg)
r+1, i, β
)
, . . . ,
(
(pβjg)
r+t, i, β
)
= (g2, i, λ2) is a path from (g1, i, λ1) to
(g2, i, λ2) in Cay(S, {a}). Similarly, if r > q, there is a path
from (g2, i, λ2) to (g1, i, λ1) in Cay(S, {a}).
(case 2) For λ1 = β, λ2 6= β. Then (g2, i, λ2)(g, j, β) = (g2pλ2jg, i, β),
and thus
(
(g2, i, λ2), (g2pλ2jg, i, β)
)
is an arc in Cay(S, {a}).
Since G = 〈pβjg〉 and g2pλ2jg ∈ G, g2pλ2jg = (pβjg)
u for some
u ∈ {1, 2, ..., |pβjg|}. By case 1, there is a path from (g1, i, λ1)
to (g2pλ2jg, i, β) or from (g2pλ2jg, i, β) to (g1, i, λ1). Therefore
we have a semipath between (g1, i, λ1) and (g2, i, λ2).
(case 3) For λ1 6= β, λ2 = β. Then (g1, i, λ1)(g, j, β) = (g1pλ1jg, i, β),
and so
(
(g1, i, λ1), (g1pλ1jg, i, β)
)
is an arc in Cay(S, {a}). Since
J. Meksawang, S. Panma, U. Knauer 67
G = 〈pβjg〉 and g1pλ1jg ∈ G, g1pλ1jg = (pβjg)
v for some
v ∈ {1, 2, ..., |pβjg|}. By case 1, there is a path from (g2, i, λ2)
to (g1pλ1jg, i, β) or from (g1pλ1jg, i, β) to (g2, i, λ2). Therefore
we have a semipath between (g1, i, λ1) and (g2, i, λ2).
(case 4) For λ1 6= β, λ2 6= β. Then (g1, i, λ1)(g, j, β) = (g1pλ1jg, i, β)
and (g2, i, λ2)(g, j, β) = (g2pλ2jg, i, β).
Thus
(
(g1, i, λ1), (g1pλ1jg, i, β)
)
and
(
(g2, i, λ2), (g2pλ2jg, i, β)
)
are arcs in Cay(S, {a}). Since g1pλ1jg, g2pλ2jg ∈ G = 〈pβjg〉,
g1pλ1jg = (pβjg)
w and g2pλ2jg = (pβjg)
z for some w, z ∈
{1, 2, ..., |pβjg|}. By case 1, there is a path from (g1pλ1jg, i, β)
to (g2pλ2jg, i, β) or from (g2pλ2jg, i, β) to (g1pλ1jg, i, β).
Therefore we have a semipath between (g1, i, λ1) and
(g2, i, λ2).
By the above four cases we conclude that Cay(S, {a}) is connected.
Acknowledgment
The first author would like to thank the Thai Government Scholaships in
the Area of Science and Technology (Ministry of Science and Technology)
and the Graduate School, Chiang Mai University. The second author the
Centre of excellence in mathematics, the Commission on Higher Education,
Thailand for their financial support during the preparation of this paper.
References
[1] Sr. Arworn, U. Knauer, N. Na Chiangmai, Characterization of Digraphs of Right
(Left) Zero Unions of Groups, Thai Journal of Mathematics, 1(2003), 131-140.
[2] N. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge 1993.
[3] G. Chartrand, L. Lesniak, Graphs and Digraphs, Chapman and Hall, London 1996.
[4] M.-C. Heydemann, Cayley graphs and interconnection networks, in G. Hahn, G.
Sabidussi (eds.), Graph Symmetry, 167-224, Kluwer 1997.
[5] A. V. Kelarev, On Undirected Cayley Graphs, Australasian Journal of Combina-
torics 25 (2002), 73-78.
[6] A. V. Kelarev, Graph Algebras and Automata, Marcel Dekker, New York, 2003.
[7] A. V. Kelarev, Labelled Cayley Graphs and Minimal Automata, Australasian
Journal of Combinatorics 30 (2004), 95-101.
[8] A. V. Kelarev, C. E. Praeger, On Transitive Cayley Graphs of Groups and Semi-
groups, European Journal of Combinatorics, 24(2003), 59-72.
[9] A. V. Kelarev, S. J. Quinn, A Combinatorial Property and Cayley Graphs of
Semigroups, Semigroup Forum, 66(2003), 89-96.
[10] M. Kilp, U. Knauer, A. V. Mikhalev, Monoids, Acts and Categories, W. de Gruyter,
Berlin 2000.
68 Characterization of finite simple semigroup.. .
[11] S. Panma, U. Knauer, Sr. Arworn, On Transitive Cayley Graphs of Right (Left)
Groups and of Clifford Semigroups, Thai Journal of Mathematics, 2(2004), 183-195.
[12] S. Panma, U. Knauer, N. Na Chiangmai, Sr. Arworn, Characterization of Clifford
Semigroup Digraphs, Discrete Mathematics, 306(2006), 1247-1252.
[13] M. Petrich, N. Reilly, Completely Regular Semigroups, J. Wiley, New York 1999.
[14] C. E. Praeger, Finite transitive permutation groups and finite vertex-transitive
graphs , in G. Hahn, G. Sabidussi (eds.), Graph Symmetry, 277-318, Kluwer 1997.
[15] G. Sabidussi, On a Class of fixed-point-free Graphs, Proc. Amer. Math. Soc.,
9(1958), 800-804.
[16] A. T. White, Graphs, Groups and Surfaces, Elsevier, Amsterdam 2001.
Contact information
J. Meksawang Department of Mathematics,
Faculty of Science, Chiang Mai University,
Chiang Mai, Thailand
E-Mail: john.npu@hotmail.com
S. Panma Department of Mathematics,
Faculty of Science, Chiang Mai University,
Chiang Mai, Thailand
and
Centre of Excellence in Mathemaitics,
CHE, Si Ayutthaya Rd.,
Bangkok 10400, Thailand
E-Mail: panmayan@yahoo.com
U. Knauer Carl von Ossietzky Universitaet,
Institut fuer Mathematik,
D-26111,Oldenburg,
Germany
E-Mail: knauer@uni-oldenburg.de
Received by the editors: 02.06.2010
and in final form 30.09.2011.
|