A problem on generalized Cayley graphs of semigroups

Abstract

Zhu (Semigroup Forum 84(3), 144–156, 2012) investigated some combinatorial properties of generalized Cayley graphs of semigroups. In Remark 3.8 of (Zhu, Semigroup Forum 84(3), 144–156, 2012), Zhu proposed the following question: It may be interesting to characterize semigroups S such that Cay(S,ω _l )=Cay(S,ω _r ). In this short note, we prove that for any regular semigroup S, Cay(S,ω _l )=Cay(S,ω _r ) if and only if S is a Clifford semigroup.

1 Introduction and main theorem

Cayley graphs of semigroups have been studied by many authors and some important results have been obtained, Kelarev-Ryan-Yearwood [2] is a good survey in this aspect. Most recently, Zhu [3] generalized the usual Cayley graphs of semigroups to generalized Cayley graphs of them and in texts [3] and [4], Zhu investigated some algebraic and combinatorial properties for such graphs. In particular some results of the usual Cayley graphs of semigroups are generalized to generalized Cayley graphs of semigroups.

Let S be an ideal of a semigroup T and ρ⊆T ¹×T ¹. Following Zhu [3], the generalized Cayley graph Cay(S,ρ) of S relative to ρ is defined as the graph with vertex set S and edge set

$$E\bigl(\mathit{Cay}(S,\rho)\bigr)=\bigl\{(a,b)\in S\times S\mid xay=b \mbox{ for some } (x,y)\in \rho\bigr\}. $$

In particular, generalized Cayley graphs Cay(S,ω _l ), Cay(S,ω _r ) and Cay(S,ω) are called left universal, right universal and universal Cayley graphs of S, respectively, where ω _l =S ¹×{1},ω _r ={1}×S ¹ and ω=S ¹×S ¹.

Zhu [3, 4] mainly investigated universal Cayley graphs of a semigroup S and obtained some useful results. On the other hand, Remark 3.8 in Zhu [4] proposes the following.

Problem

It may be interesting to characterize semigroups S such that Cay(S,ω _l )=Cay(S,ω _r ).

Obviously, the above problem is trivial for commutative semigroups. As we have known, regular semigroups play a major role in the algebraic theory of semigroups. In this short note, we give an answer to this problem for regular semigroups. Recall that a semigroup is regular if there exists x∈S such that axa=a and xax=x for any a∈S. A Clifford semigroup is a regular semigroup S in which ae=ea for every idempotent e and every a in S. Here is our result.

Theorem

For any regular semigroup S, Cay(S,ω _l )=Cay(S,ω _r ) if and only if S is a Clifford semigroup.

2 A proof

To give a proof of the theorem, we need to recall the following two well-known results. On one hand, from Chap. IV, Exercise 2 in Howie [1], we can obtain the following lemma.

Lemma 1

(See Howie [1, p. 125])

Let S be a regular semigroup. Then S is a Clifford semigroup if and only if ${\mathcal{L}}=\mathcal{R}$.

On the other hand, from Chap. IV, Theorem 2.1 in Howie [1], we have another characterization of Clifford semigroups as follows. On the notion of strong semilattice of semigroups, the reader is referred to Chap. IV in Howie [1].

Lemma 2

(See Howie [1, p. 94])

A semigroup S is a Clifford semigroup if and only if S=(G _α ,Y,ϕ _α,β ) is a strong semilattice of groups.

Now we can give a proof of the Theorem.

Necessity. Assume that S is a regular semigroup and Cay(S,ω _l )=Cay(S,ω _r ). If a,b∈S and $a{\mathcal{L}}b$, then a=xb and b=ya for some x,y∈S ¹. This implies that (a,b),(b,a)∈E(Cay(S,ω _l )). By hypothesis, (a,b),(b,a)∈E(Cay(S,ω _r )). Therefore, there exist x′,y′∈S ¹ such that b=ax′ and a=by′. This yields that $a{\mathcal{R}} b$. We have shown that ${\mathcal{L}}\subseteq {\mathcal{R}}$. By a dual argument, we can obtain ${\mathcal{R}}\subseteq {\mathcal{L}}$. Thus ${\mathcal{L}}=\mathcal{R}$. Since S is regular, it follows that S is a Clifford semigroup from Lemma 1.

Sufficiency. Assume that S=(G _α ,Y,ϕ _α,β ) is a Clifford semigroup by Lemma 2 and let a,b∈S. Suppose that (a,b)∈E(Cay(S,ω _l )). Then xa=b for some x∈S ¹. If x=1, then ax=b and so (a,b)∈E(Cay(S,ω _r )). Now, let x∈G _α and a∈G _β . Then b∈G _αβ and b=xa=(xϕ _α,αβ )(aϕ _β,αβ ). Denote y=(aϕ _β,αβ )⁻¹(xϕ _α,αβ )(aϕ _β,αβ ), where (aϕ _β,αβ )⁻¹ is the inverse of aϕ _β,αβ in the group G _αβ . Then y∈G _αβ , and

This implies that (a,b)∈E(Cay(S,ω _r )). Therefore E(Cay(S,ω _l ))⊆E(Cay(S,ω _r )). By a dual argument, we can obtain E(Cay(S,ω _r ))⊆E(Cay(S,ω _l )). This completes our proof.

Remark 1

From the proof of “necessity” part above, we can see that ${\mathcal{L}} ={\mathcal{R}}$ for any semigroup S with Cay(S,ω _l )=Cay(S,ω _r ). The following example illustrates that there exists a semigroup S with ${\mathcal{L}} ={\mathcal{R}}$ which does not satisfy Cay(S,ω _l )=Cay(S,ω _r ). In fact, let S be the free monoid generated by the two symbols 0 and 1. Then Green’s relations ${\mathcal{L}}$ and ${\mathcal{R}}$ are equal on S (both of them are identity relation on S). Obviously, (0,10)∈E(Cay(S,ω _l )). However, $(0,10)\not\in E(\mathit{Cay}(S,\omega_{r}))$.

Remark 2

Necessary and sufficient conditions for Cay(S,ω _l ) and Cay(S,ω _r ) to be isomorphic are not known. The following example shows that this graph isomorphism may exist for a regular semigroup which is not a Clifford semigroup.

Example

Consider the 4-element rectangular band {e,f,g,h} with $e{\mathcal{R}}f$, $e{\mathcal{L}}g$, $g{\mathcal{R}} h$ and $f{\mathcal{L}}h$. For this semigroup, Cay(S,ω _l ) is the disjoint union of the complete directed graphs with vertex sets {e,g} and {f,h}, with a loop at each vertex, while Cay(S,ω _r ) is the disjoint union of the complete directed graphs with vertex sets {e,f} and {g,h} and with a loop at each vertex. So the two graphs are isomorphic.