On transitive generalized Cayley graphs of semigroups

Abstract

Generalized Cayley graphs of semigroups were first defined by Zhu (Semigroup Forum 84:131–143, 2012) and further studied by Zhu (Semigroup Forum 84:144–156, 2012) as well as by Wang (Semigroup Forum 86:221–223, 2013). In the present paper, we study the vertex-transitivity of generalized Cayley graphs of a semigroup so that two main theorems of Kelarev and Praeger (Eur J Comb 24:59–72, 2003) for the classical and well known Cayley graphs of semigroups are extended to those for generalized Cayley graphs of a semigroup.

1 Introduction

As an analogue of the notion of Cayley graphs of a group (see for example, [4, 16]), the Cayley graph $\text {Cay}(G, S)$ of a semigroup G relative to its subset S is defined as the graph with vertex set G and edge set E(S) consisting of those ordered pairs (a, b) such that $xa = b$ for some $x \in S$ (see, for example [6, 7, 9–13]). Cayley graphs are the most important class of graphs associated to semigroups because of their practical applications and relations to automata theory (cf. [7, 8, 11]). This concept was extended to generalized Cayley graphs of a semigroup by the author in [17], where some fundamental properties of generalized Cayley graphs of semigroups were studied. Recall that if S is an ideal of a semigroup T, then we call T an ideal extension of S. Notice that, in the whole paper, $T^1$ always stands for the semigroup T with identity adjoined if necessary. The definition of the generalized Cayley graphs of semigroups is as follows.

Definition 1.1

(Definition 1.1 of [17]) Let T be an ideal extension of a semigroup S and $\rho \subseteq T^1\times T^1$. The generalized Cayley graph $\text {Cay}(S, \rho )$ of S relative to $\rho$ is defined as the graph with vertex set S and edge set $E(\text {Cay}(S, \rho ))$ consisting of those ordered pairs (a, b) such that $xay = b$ for some $(x, y)\in \rho$.

For example, if G is a semigroup with S a nonempty subset of G, then the generalized Cayley graph $\text {Cay}(G,S\times \{1\})$ is actually the classical and well known Cayley graph ${\text {C}ay}(G,S)$.

In [18], some combinatorial issues related to generalized Cayley graphs were addressed. In [18, Remark 3.8], the author proposed characterizing semigroups S such that $Cay(S,S_l)=Cay(S,S_r)$, where $S_l=S^1\times \{1\}$ and $S_r= \{1\}\times S^1$ are the left and right universal relations on $S^1$, respectively. This problem was partially solved by Wang in [15], where it was proved that for any regular semigroup S, $Cay(S,S_l)=Cay(S,S_r)$ if and only if S is a Clifford semigroup, i.e., a semilattice of groups. This result was further extended by the author in [19]. Generalized Cayley graphs of rectangular groups were characterized in [20].

The aim of this paper is to study certain transitivity properties, which we shall define below, of generalized Cayley graphs of semigroups so that the main results of Kelarev and Praeger in [10] for the classical and well known Cayley graphs of semigroups are generalized to those for generalized Cayley graphs.

Let us begin with some basic concepts.

Let D(V, E) be a graph with vertex set V and edge set $E \subseteq V \times V$. If $U\subseteq V$, then the induced subgraph of U in D is defined as the graph with vertex set U and edge set $\{(u_1,u_2)|u_1,u_2\in U \text { and } (u_1,u_2)\in E\}$. Sometimes we equate the induced subgraph of U with the vertex set U. A mapping $\phi : V\longrightarrow V$ is called an endomorphism of the graph D if $(u^\phi , v^\phi ) \in E$ for all $(u, v)\in E$. If $\phi$ is not only an endomorphism of the graph D but also a bijection from V onto V itself and if $\phi ^{-1}$ is also an endomorphism of the graph D, then we call $\phi$ an automorphism of the graph D.

A graph D(V, E) is said to be vertex-transitive if, for any two vertices $x, y \in V$, there exists an automorphism $\phi \in \text {Aut}(D)$ such that $x^\phi = y$ (see [1] or [10]). More generally, a subset A of $\text {End}(D)$ is said to be vertex-transitive on D, and D is said to be A-vertex-transitive if, for any two vertices $x, y \in V$, there exists an endomorphism $\phi \in A$ such that $x^\phi = y$ (see [2, Section 11.1] or [10]).

Now let G be a semigroup and let $S \subseteq G$. As in [10], denote the automorphism group (endomorphism monoid) of $\text {Cay}(G, S)$ by $\text {Aut}_S(G)$ (respectively, $\text {End}_S(G))$. Thus

$$\begin{aligned} \text {Aut}_S(G) = \text {Aut}(\text {Cay}(G, S)) \text { and } {\text { End}}_S(G) = \text {End}(\text {Cay}(G, S)). \end{aligned}$$

More generally, let T be an ideal extension of a semigroup S and let $\rho \subseteq T^1\times T^1$. Denote the automorphism group (endomorphism monoid) of the generalized Cayley graph $\text {Cay}(S, \rho )$ by $\text {Aut}_\rho (S)$ (respectively, $\text {End}_\rho (S))$. That is,

$$\begin{aligned} \text {Aut}_\rho (S) = \text {Aut}(\text {Cay}(S, \rho )) \text { and } {\text { End}}_\rho (S) = \text {End}(\text {Cay}(S, \rho )). \end{aligned}$$

It is clear that

$$\begin{aligned} \text {Aut}_\rho (S)\subseteq \text {End}_\rho (S). \end{aligned}$$

As in [10], an element $\phi \in \text {End}_S(G)$ is called a colour-preserving endomorphism if $sx = y$ implies $s(x^\phi ) = y^\phi$, for every $x, y \in G$ and $s \in S$. If we regard an edge (x, sx), for $s \in S$, as having ‘colour’ s, so that the elements of S are thought of as colours associated with the edges of the Cayley graph, then every colour-preserving endomorphism maps each edge to an edge of the same colour. Denote by $\text {ColEnd}_S(G)$ (and $\text {ColAut}_S(G))$ the sets of all colour-preserving endomorphisms (respectively, automorphisms) of $\text {Cay}(G, S)$. Similarly, when T is an ideal extension of a semigroup S and $\rho \subseteq T^1\times T^1$, an element $\phi \in \text {End}_\rho (S)$ will be called a colour-preserving endomorphism if $x^\alpha = y$ implies $(x^\phi )^\alpha = y^\phi$, for every $x, y \in S$ and $\alpha \in \rho$. Denote by $\text {ColEnd}\rho (S)$ (and $\text {ColAut}\rho (S))$ the sets of all colour-preserving endomorphisms (respectively, automorphisms) of $\text {Cay}(S, \rho )$. Evidently,

$$\begin{aligned} \text {ColAut}\rho (S))\subseteq \text {ColEnd}\rho (S). \end{aligned}$$

Vertex-transitivity of Cayley graphs of groups has received much attention in the literature and many interesting results have been obtained, see for example [1, 2, 14]. Also, there have been many research articles on vertex-transitivity of Cayley graphs of semigroups, see [3, 10, 12, 13]. In particular, [10, Theorems 2.1 and 2.2] describe all semigroups G and all subsets S of G, satisfying a certain finiteness condition, such that the Cayley graph $\text {Cay}(G, S)$ is $\text {ColAut}_S(G)$-vertex-transitive and $\text {Aut}_S(G)$-vertex-transitive respectively. In the present paper, we find the equivalent conditions for the generalized Cayley graph $\text {Cay}(S,\rho )$ to be $\text {ColAut}_\rho (S)$-vertex-transitive and $\text {Aut}_\rho (S)$-vertex-transitive, respectively. Our main results are Theorems 6.1 and 6.2, which generalize Theorems 2.1 and 2.2 of [10] respectively. The latter are presented as two corollaries in this paper, see Corollaries 7.1 and 7.2.

In the next section we list the background theory on semigroups needed for our arguments. Then we prove some general results about generalized Cayley graphs of semigroups in Sects. 3 and 4. For establishing our main theorems, some new notions are needed, which we shall introduce in Sect. 5. In Sect. 6, we present and prove two main theorems of this paper. As two important applications of our main theorems, we present and reprove the main results of [9] in Sect. 7. At last, as one more application of our main theorems, an example is given in Sect. 8.

2 Preliminaries on semigroups

In the whole paper, we always use standard notions and notation of semigroup theory following [2, 5]. But in this section, we only introduce a few related notions, notation and known facts required for the arguments of the subsequent sections.

Recall that if S is a semigroup and $A \subseteq S$, then the subsemigroup generated by A in S is denoted by $\langle S\rangle$. An element a of a semigroup G is said to be periodic if there exist positive integers m, n such that $a^{m+n} = a^m$. A subset S of G is periodic if every element of S is periodic. In particular, if all principal left ideals of a semigroup are finite, then the semigroup is periodic. An element x of a semigroup is called an idempotent if $x^2=x$. A band is a semigroup entirely consisting of idempotents. A band is called a left zero (right zero, rectangular) band if it satisfies the identity $xy = x$ (respectively, $xy = y$, $xyx = x$). Among all elements of a band there is a natural (partial) order defined by $e\le f$ if and only if $ef=fe=e$. A semigroup is said to be (left, right) simple if it has no proper (left, right) ideals. A semigroup is left (right) cancellative if $xy = xz$ (respectively, $yx = zx$) implies $y = z$, for all $x, y, z \in S$. A semigroup is called a right (left) group if it is right (left) simple and left (right) cancellative.

Lemma 2.1

(Corollary 3.1.2 of [5]) Let S be a semigroup. Then following statements hold:

• (i) S is simple if and only if $SaS=S$ for all $a\in S$;

• (ii) S is left simple if and only if $Sa=S$ for all $a\in S$;

• (iii) S is right simple if and only if $aS=S$ for all $a\in S$.

Lemma 2.2

(Theorem 1.27 of [2]) For any periodic semigroup S, the following statements are equivalent:

• (i) S is right (left) simple;

• (ii) S is a right (left) group;

• (iii) S is isomorphic to the direct product of a right (left) zero band and a group.

Let S be a semigroup. An idempotent of S is said to be primitive if it is minimal with respect to the natural order within the set of all idempotents of S. If S contains a primitive idempotent and if it is simple, then we say that S is completely simple. The following lemma is a simplified version of the Rees Theorem, due in effect to A. K. Suschkewitsch:

Lemma 2.3

(Theorem 3.3.1 of [5]) Let G be a group, let I, $\varLambda$ be nonempty sets and let $P=(p_{\lambda ,i})$ be a $\varLambda \times I$ matrix with entries in G. Let $S=(I\times G\times \varLambda )$, and define a multiplication on S by

$$\begin{aligned} (i,a,\lambda )(j,b,\mu )=(i,ap_{\lambda j}b,\mu ). \end{aligned}$$

Then S is a completely simple semigroup.

Conversely, every completely simple semigroup is isomorphic to a semigroup constructed in this way.

We denote the semigroup $I\times G\times \varLambda$ with the given multiplication by ${\mathscr {M}}[G;I,\varLambda ; P]$.

Lemma 2.4

(Theorem 3.2.11 of [5]) A periodic semigroup is simple if and only if it is completely simple.

3 General properties of generalized Cayley graphs

Let $D = (V, E)$ be a graph. The underlying undirected graph of D has the same vertex set V and it has an undirected edge $\{u, v\}$ for each directed edge (u, v) of D. The graph D is said to be connected if its underlying undirected graph is connected. If, for each pair of vertices u, v of D, there exists a directed path from u to v, then D is said to be strongly connected.

If S is a semigroup with respect to the multiplication $\cdot$, then the anti-semigroup of S, denoted by $S^*$, is defined as the semigroup $(S,*)$, where the multiplication $*$ is defined by $a*b=b\cdot a$ for any $a,b\in S$. Let T be an ideal extension of a semigroup S and $\rho \subseteq T^1\times T^1$. Then by $[\rho \rangle$ we denote the subsemigroup generated by $\rho$ in the direct product $(T^1)^*\times T^1$; dually, by $\langle \rho ]$ we denote the subsemigroup generated by $\rho$ in the direct product $T^1\times (T^1)^*$, where $T^1$ stands for the semigroup T with identity adjoined if necessary, and where $(T^1)^*$ is the anti-semigroup of $T^1$. Let $a\in S$. Then by $C_a$ we denote the set of all vertices b of the generalized Cayley graph $\text {Cay}(S, \rho )$ such that there exists a directed path from a to b. Set

$$\begin{aligned} a^{[\rho \rangle }=\{xay| (x,y)\in [\rho \rangle \}\subseteq S. \end{aligned}$$

The following lemma generalizes [10, Lemma 5.1].

Lemma 3.1

If T is an ideal extension of a semigroup S and $\rho \subseteq T^1\times T^1$, then for any $a\in S$,

$$\begin{aligned} C_a=a^{[\rho \rangle }. \end{aligned}$$

Proof

Take any $b\in C_a$. There exists a directed path $a = v_1, v_2, \ldots , v_n = b$, where $n > 1$. By the definition of the generalized Cayley graph $\text {Cay}(S, \rho )$ we get $v_{i+1} = v_i^{\alpha _i}$, for $i = 1, \ldots , n-1$ and some $\alpha _i \in \rho$. Hence $b=a^{\alpha _1\ldots \alpha _{n-1}}$, and so $b \in a^{[\rho \rangle }$. This shows that $C_a\subseteq a^{[\rho \rangle }$.

Conversely, pick any $b \in a^{[\rho \rangle }$. Since $[\rho \rangle$ is generated by $\rho$, there exist $\alpha _1, \ldots , \alpha _{n-1} \in \rho$ such that $b=a^{\alpha _1\ldots \alpha _{n-1}}$, where $n > 1$. Setting $v_1 = a$ and $v_{i+1} = v_i^{\alpha _i}$ for $i = 1, \ldots , n-1$, we see that $v_n =b$ and

$$\begin{aligned} (a, a^{\alpha _1}), (a^{\alpha _1}, a^{\alpha _1\alpha _2}), \ldots , (a^{\alpha _1\ldots \alpha _{n-2}}, b) \end{aligned}$$

are the edges of $\text {Cay}(S, \rho )$. Therefore $a = v_1, v_2, \ldots , v_n = b$ is a directed path from a to b in $\text {Cay}(S, \rho )$. This shows that $a^{[\rho \rangle }\subseteq C_a$. Therefore, $C_a=a^{[\rho \rangle }$, as required. $\square$

The next lemma may be regarded as a generalization of [10, Lemma 5.2]. But both have a very big difference for under present circumstances the concept of (completely) simple semigroups does not come in handy.

Lemma 3.2

Let T be an ideal extension of a semigroup S and $\rho \subseteq T^1\times T^1$ with the property:

$$\begin{aligned} u^{\alpha }\in u^{\alpha \beta [\rho \rangle } \,{\text { for all }}\, \alpha ,\beta \in [\rho \rangle \,{\text { and all }}\, u\in S. \end{aligned}$$

Suppose that $S^\rho = S$. Then every connected component of $\text {Cay}(S,\rho )$ is strongly connected and, for each $v \in S$, the connected component containing v is equal to $C_v=v^{[\rho \rangle } = v^{\alpha [\rho \rangle }$ for any $\alpha \in [\rho \rangle$.

Proof

Let (u, v) be any edge of $\text {Cay}(S,\rho )$. Then $v = u^{\alpha }$ for some $\alpha \in \rho$. Since $S^\rho = S$, we can find elements $\beta \in \rho$, $u_1\in S$ such that $u_1^\beta =u$. Hence $v = u_1^{\beta \alpha }$. Since $u_1^{\beta }\in u_1^{\beta \alpha [\rho \rangle }$, there exists $\gamma \in [\rho \rangle$ such that $u_1^\beta =u_1^{\beta \alpha \gamma }$. Hence $u=u_1^\beta =u_1^{\beta \alpha \gamma }=(u_1^{\beta \alpha })^{\gamma }=v^{\gamma }\in v^{[\rho \rangle }=C_v$. By the definition of $C_v$, there exists a directed path from v to u. Since (u, v) was chosen arbitrarily, it follows that every connected component of $\text {Cay}(S,\rho )$ is strongly connected.

Let C be the set of vertices of a connected component of $\text {Cay}(S,\rho )$, and let $v\in C$. Since C is strongly connected, it follows from Lemma 3.1 that $C = C_v=v^{[\rho \rangle }$. Given that $S^\rho = S$, there exist $u\in S, \beta \in \rho$ such that $u^\beta = v$. Since $u^{\beta }\in u^{\beta \alpha [\rho \rangle }$, $v \in v^{\alpha [\rho \rangle }$. It follows that $v^{[\rho \rangle } = v^{\alpha [\rho \rangle }$. Therefore $C=C_v=v^{[\rho \rangle } = v^{\alpha [\rho \rangle }$, which completes the proof. $\square$

The following two lemmas are generalizations of [10, Lemmas 5.4 and 5.5] respectively.

Lemma 3.3

Let T be an ideal extension of a semigroup S and $\alpha \in T^1\times T^1$ be a periodic element such that $S^\alpha =S$, and let I be a subset of S such that $I^\alpha \subseteq I$, then $(S\setminus I)^\alpha \subseteq (S\setminus I)$.

Proof

Since $\alpha$ is periodic, there exist positive integers m and n such that $\alpha ^{m+n} = \alpha ^m$. Take any element $u\in (S\setminus I)$ and suppose to the contrary that $u^\alpha \in I$. Then $u^{\alpha ^n}\in I$ by the assumption that $I^\alpha \subseteq I$. Since $S^\alpha =S$, we have $S^{\alpha ^m}=S$, which means that there exists $v\in S$ such that $v^{\alpha ^m}=u$. Since $I^\alpha \subseteq I$, we have $I^{\alpha ^m}\subseteq I$. It follows that $v\in S\setminus I$. Since $\alpha ^{m+n} = \alpha ^m$, we get $u^{\alpha ^{n}} = (v^{\alpha ^m})^{\alpha ^{n}}=v^{\alpha ^{m+n}}=v^{\alpha ^m}=u$. Then the assumption that $u\in (S\setminus I)$ contradicts that $u^{\alpha ^n}\in I$. This shows that $(S\setminus I)^\alpha \subseteq (S\setminus I)$. $\square$

Lemma 3.4

Let T be an ideal extension of a semigroup S, let $\rho \subseteq T^1\times T^1$ be a periodic subset such that $S^\alpha =S$ for every $\alpha \in \rho$, and let I be a subset of S such that $I^\rho \subseteq I$. Then I is a union of connected components of $\text {Cay}(S,\rho )$. In particular, for every $a\in S$, $C_a$ is a connected component of $\text {Cay}(S,\rho )$.

Proof

Take any edge (u, v) of $\text {Cay}(S,\rho )$. Then $v=u^\alpha$, for some $\alpha \in \rho$. Since $I^\rho \subseteq I$ and by Lemma 3.3, we get that $u\in I\Longleftrightarrow v\in I$, which means that all vertices of I are adjacent to vertices of I only. Hence I is a union of connected components of $\text {Cay}(S,\rho )$. Let $a\in S$. Then in light of Lemma 3.1, $C_a=a^{[\rho \rangle }$ for each $a\in S$. It follows that $(C_a)^\rho \subseteq C_a$. Thus $C_a$ is a union of connected components of $\text {Cay}(S,\rho )$. It is evident that $C_a$ itself is connected. So the final assertion of the lemma follows. $\square$

4 Transitivity properties of generalized Cayley graphs

In this section we prove several preparatory lemmas for the proof of the main theorems, involving transitivity of generalized Cayley graphs of semigroups.

The following three lemmas extend [10, Lemmas 6.1, 6.2 and 6.3], respectively.

Lemma 4.1

Let T be an ideal extension of a semigroup S and $\rho \subseteq T^1\times T^1$.

• (i) If $\text {End}_\rho (S)$ is vertex-transitive on $\text {Cay}(S,\rho )$, then $S^\rho =S$.

• (ii) If $\text {ColEnd}_\rho (S)$ is vertex-transitive on $\text {Cay}(S,\rho )$, then $S^\alpha =S$ for each $\alpha \in \rho$.

Proof

Pick any $u \in S$ and $\alpha \in \rho$. Then $\phi (u^\alpha ) = u$ for some $\phi \in \text {End}_\rho (S)$. Since $(u, u^\alpha )$ is an edge of $\text {Cay}(S,\rho )$, so is $(\phi (u), \phi (u^\alpha ))$. Hence $(\phi (u))^\beta =\phi (u^\alpha )$ for some $\beta \in \rho$. Thus $u =\phi (u^\alpha )=(\phi (u))^\beta \in S^\rho$, and so $S^\rho =S$, i.e. (i) holds.

Furthermore, if $\text {ColEnd}_\rho (S)$ is vertex-transitive on $\text {Cay}(S,\rho )$, then we may assume that $\phi \in \text {ColEnd}_\rho (S)$, whence one may choose $\beta$ such that $\beta =\alpha$, and so $u =\phi (u^\alpha )=(\phi (u))^\alpha \in S^\alpha$. Therefore, $S^\alpha =S$, i.e. (ii) holds. $\square$

Lemma 4.2

Let T be an ideal extension of a semigroup S and $\rho$ a periodic subset of $T^1\times T^1$ such that $\text {ColEnd}_\rho (S)$ is vertex-transitive on $\text {Cay}(S,\rho )$. Then $u^{[\rho \rangle }=u^{[\rho \rangle \alpha }$ for each $u\in S$ and each $\alpha \in [\rho \rangle$.

Proof

For each $\alpha \in \rho$, $S^\alpha =S$ by Lemma 4.1. Then for each $u\in S$ and $\beta \in [\rho \rangle$, there exists $v\in S$ such that $v^\alpha = u^\beta$. By transitivity, $v=\phi (u)$ for some $\phi \in \text {ColEnd}_\rho (S)$. Hence $(\phi (u))^\alpha =v^\alpha =u^\beta \in u^{[\rho \rangle }$, and it follows from Lemma 3.3 (with $I =u^{[\rho \rangle }$) that $\phi (u)\in u^{[\rho \rangle }$. This means that $u^\beta \in u^{[\rho \rangle \alpha }$. Hence $u^{[\rho \rangle }\subseteq u^{[\rho \rangle \alpha }$. Notice that the converse inclusion is evidently true. Thus $u^{[\rho \rangle }=u^{[\rho \rangle \alpha }$ for all $\alpha \in \rho$. By induction we deduce that $u^{[\rho \rangle }=u^{[\rho \rangle \alpha }$ for all $\alpha \in [\rho \rangle$, which completes the proof. $\square$

Lemma 4.3

Let T be an ideal extension of a semigroup S and $\rho$ a subset of $T^1\times T^1$ such that all principal right ideals of $[\rho \rangle$ are finite, and suppose that the generalized Cayley graph $\text {Cay}(S,\rho )$ is $\text {Aut}_\rho (S)$-vertex-transitive. Then the following statements hold:

• (i) for any $u\in S$, the connected component containing u is $C_u=u^{[\rho \rangle }$, which is strongly connected;

• (ii) $u^\alpha \in u^{\alpha \beta [\rho \rangle }$ for any $u\in S$ and any $\alpha , \beta \in [\rho \rangle$;

• (iii) $C_u=u^{[\rho \rangle }=u^{\alpha [\rho \rangle }=u^{[\rho \rangle \alpha [\rho \rangle }$ for any $u\in S$ and any $\alpha \in [\rho \rangle$;

• (iv) $S=S^{[\rho \rangle }=S^{\alpha [\rho \rangle }=S^{[\rho \rangle \alpha [\rho \rangle }$ for any $\alpha \in [\rho \rangle$.

Proof

Clearly, the condition that all the principal right ideals of $[\rho \rangle$ are finite implies that $[\rho \rangle$ is periodic. Take any element $u\in S$. By Lemma 3.1, $C_u=u^{[\rho \rangle }$. By Lemma 4.1, $S^\rho = S$, and so there exists $a \in S$, $\alpha \in \rho$, such that $a^\alpha = u$. Since the principal right ideal $\alpha [\rho \rangle ^1$ is finite, so is $\alpha [\rho \rangle$. Thus, $C_u = u^{[\rho \rangle }=a^{\alpha [\rho \rangle }$ is finite. Since $\text {Cay}(S,\rho )$ is $\text {Aut}_S(G)$-vertex-transitive, we get $|C_u| = |C_v|$ for all $v \in S$. If $v \in C_u$, then evidently $C_v \subseteq C_u$. It follows that $C_v = C_u$, so $v\in C_v$. Also $u \in C_u$. Therefore $C_u$ is strongly connected. Moreover, if $C_u$ and $C_v$ have a common vertex w for some $v \in S$, then $C_u=C_w=C_v$. Hence $C_u\cup C_v=C_u$, which implies that $C_u$ is a connected component of $\text {Cay}(S,\rho )$. Thus (i) is proved.

Pick any $\alpha ,\beta \in [\rho \rangle$ and any $u\in S$. Since $u^{\beta \alpha } \in u^{\beta [\rho \rangle }=C_{u^{\beta }}$, $C_{u^{\beta \alpha }}= C_{u^{\beta }}$ by the last paragraph. It follows that $u^{\beta \alpha [\rho \rangle }= u^{\beta [\rho \rangle }$. Since $u^{\beta }\in C_{u^{\beta }}$, $u^{\beta }\in C_{u^{\beta \alpha }}$, we get $u^\beta \in u^{\beta \alpha [\rho \rangle }$. Hence $u^\beta \subseteq u^{[\rho \rangle \alpha [\rho \rangle }$, and so $u^{[\rho \rangle }\subseteq u^{[\rho \rangle \alpha [\rho \rangle }.$ Noticing that the converse inclusion is obviously true, we get actually that $u^{[\rho \rangle }= u^{[\rho \rangle \alpha [\rho \rangle }$. Since $u^\alpha \in u^{[\rho \rangle }$, $C_u=C_{u^\alpha }$, that is, $u^{[\rho \rangle }= u^{\alpha [\rho \rangle }$. Therefore, (ii) and (iii) are true.

Since $S^\rho = S$, by induction we deduce that $S^{[\rho \rangle } = S$. Pick any $\alpha \in [\rho \rangle$ and any $u\in S$. By (iii), we have that $C_u=u^{[\rho \rangle }=u^{\alpha [\rho \rangle }=u^{[\rho \rangle \alpha [\rho \rangle }$. Consequently, taking into account that $S^{[\rho \rangle }=\bigcup _{u\in S}u^{[\rho \rangle }=\bigcup _{u\in S}C_u$, we get $S=S^{[\rho \rangle }=S^{\alpha [\rho \rangle }=S^{[\rho \rangle \alpha [\rho \rangle }$. That is, (iv) follows and the proof is complete. $\square$

5 The view of actions

Dealing with the generalized Cayley graphs of semigroups is much more difficult than with the classical and well known Cayley graphs of semigroups. One of reasons is that the notion of (left, right) simple semigroups fails to apply. In order to overcome this difficulty, we adopt the view of actions, which will be defined below, so that we can generalize the concept of simplicity.

An action of a semigroup S on a set X is defined as a homomorphism $\lambda : S\longrightarrow F(X)$, $s\longmapsto \lambda (s)$, where F(X) is the semigroup of all mappings from X into X itself with respect to the composition of mappings. For simplicity, the image of any $x\in X$ under a mapping $\lambda (s)$ with $s\in S$ is denoted by $x^s$. Then we have $x^{st}=(x^s)^t$ for all $x\in X$ and for all $s,t\in S$.

For example, let T be an ideal extension of a semigroup S and $\rho$ a subset of $T^1\times T^1$. For any $\alpha =(x,y)\in [\rho \rangle$ and for any $u\in S$, define $u^\alpha =xuy$. Then $[\rho \rangle$ has an action on S in a natural manner. In the whole paper, any action of $[\rho \rangle$ on S always means this natural action. Now we can introduce the following new notions, which generalize those of (left, right) simple semigroups.

Definition 5.1

Let T be an ideal extension of a semigroup S and $\rho$ a nonempty subset of $T^1\times T^1$. We say that the action of $[\rho \rangle$ on S is right simple if $u^{[\rho \rangle }=u^{\alpha [\rho \rangle }$ for each $u\in S$ and each $\alpha \in [\rho \rangle$; left simple if $u^{[\rho \rangle }=u^{[\rho \rangle \alpha }$ for each $u\in S$ and each $\alpha \in [\rho \rangle$; and simple if $u^{[\rho \rangle }=u^{[\rho \rangle \alpha [\rho \rangle }$ for each $u\in S$ and each $\alpha \in [\rho \rangle$.

For example, if $[\rho \rangle$ is a (right, left) simple semigroup then the action of $[\rho \rangle$ on S is (right, left) simple by Lemma 2.1. It is clear that if an action of $[\rho \rangle$ on S is right simple or left simple, then it is also simple. The next lemma gives some equivalent characterizations of a right simple action $[\rho \rangle$ on S under certain conditions.

Lemma 5.2

Let T be an ideal extension of a semigroup S and $\rho$ a subset of $T^1\times T^1$ such that $S=S^{\rho }$. Then the following conditions are equivalent:

• (i) every connected component of $\text {Cay}(S,\rho )$ is strongly connected;

• (ii) for every $u\in S$, $u\in C_u=u^{[\rho \rangle }$;

• (iii) the the action of $[\rho \rangle$ on S is right simple;

• (iv) for each $\alpha \in [\rho \rangle$, there exists $\beta \in [\rho \rangle$ such that $u^{\alpha }=u^{\alpha \beta }$.

• (v) $u^\alpha \in u^{\alpha \beta [\rho \rangle }$ for any $u\in S$ and any $\alpha , \beta \in [\rho \rangle$;

Proof

Assume that (i) is true and let $u\in S$, $v\in C_u$. By definition of $C_u$, there exists a directed path from u to v. It follows that u, v are in a same connected component of the generalized Cayley graph $\text {Cay}(S,\rho )$. Since every connected component of $\text {Cay}(S,\rho )$ is strongly connected by assumption, there exists a directed path from v to u, hence also there exists a directed path from u to u itself, that is, $u\in C_u$. On the other hand, by Lemma 3.1, $C_u=u^{[\rho \rangle }$. Therefore, (ii) holds.

For showing that (ii) implies (iv), let $u\in S$ and $\alpha \in [\rho \rangle$. By (ii), $u^\alpha \in C_{u^\alpha }$. By Lemma 3.1 again, $C_{u^\alpha }=(u^\alpha )^{[\rho \rangle }$. So, $u^\alpha \in (u^\alpha )^{[\rho \rangle }=u^{\alpha [\rho \rangle }$. Thus there exists $\beta \in [\rho \rangle$ such that $u^\alpha =u^{\alpha \beta }$, which means that (iv) holds.

Obviously, (iii) implies (vi) and (iv) implies (v).

Suppose that (v) holds. Then $u^\alpha \in u^{\alpha \beta [\rho \rangle }$ for any $u\in S$ and any $\alpha , \beta \in [\rho \rangle$. Since $S=S^\rho$ and by Lemma 3.2, every connected component of $\text {Cay}(S,\rho )$ is strongly connected. So, (v) implies (i).

For showing that (v) implies (iii), let $u\in S$ and $\alpha \in [\rho \rangle$. Put $v = u^{\alpha }$. Then $v\in C_u$. It follows that $C_v\subseteq C_u$ Since $S^\rho = S$, we can find elements $\beta \in \rho$, $u_1\in S$ such that $u_1^\beta =u$. Hence $v = u_1^{\beta \alpha }$. By (v), $u_1^{\beta }\in u_1^{\beta \alpha [\rho \rangle }$. Thus there exists $\gamma \in [\rho \rangle$ such that $u_1^\beta =u_1^{\beta \alpha \gamma }$. Hence $u=u_1^\beta =u_1^{\beta \alpha \gamma }=(u_1^{\beta \alpha })^{\gamma }=v^{\gamma }\in v^{[\rho \rangle }=C_v$. It follows that $C_u\subseteq C_v$, which means that $C_u=C_v$. Hence $u^{[\rho \rangle }=v^{[\rho \rangle }$, which implies that $u^{[\rho \rangle }=u^{\alpha [\rho \rangle }$. Thus the action of $[\rho \rangle$ on S is right simple and (iii) follows. This competes the proof. $\square$

As a direct consequence of Lemma 4.3, we have the following

Corollary 5.3

Let T be an ideal extension of a semigroup S and $\rho$ a subset of $T^1\times T^1$ such that all principal right ideals of $[\rho \rangle$ are finite, and suppose that the generalized Cayley graph $\text {Cay}(S,\rho )$ is $\text {Aut}_\rho (S)$-vertex-transitive. Then the the action of $[\rho \rangle$ on S is right simple.

Also, we rewrite Lemma 4.2 in the following corollary.

Corollary 5.4

Let T be an ideal extension of a semigroup S and $\rho$ a periodic subset of $T^1\times T^1$ such that $\text {ColEnd}_\rho (S)$ is vertex-transitive on $\text {Cay}(S,\rho )$. Then the the action of $[\rho \rangle$ on S is left simple.

6 Main theorems

Now we present our main results in two theorems which describe the equivalent conditions for a generalized Cayley graph $\text {Cay}(S,\rho )$ to be $\text {ColAut}_\rho (S)$-vertex-transitive and $\text {Aut}_\rho (S)$-vertex-transitive respectively. These two theorems generalize the main results of [10]. Speaking specifically, Theorem 6.1 and Theorem 6.2 generalize [10, Theorem 2.1] and [10, Theorem 2.2], respectively.

Theorem 6.1

Let T be an ideal extension of a semigroup S and $\rho$ a nonempty subset of $T^1\times T^1$ such that all principal right ideals of $[\rho \rangle$ are finite. Then, the generalized Cayley graph $\text {Cay}(S,\rho )$ is $\text {ColAut}_\rho (S)$-vertex-transitive if and only if the following conditions hold:

• (i) for any $\alpha \in \rho$, $S^\alpha =S$;

• (ii) the action of $[\rho \rangle$ on S is right simple;

• (iii) the action of $[\rho \rangle$ on S is left simple;

• (iv) for any $u,v\in S$ and $\alpha ,\beta \in [\rho \rangle$, $u^{\alpha }=u^{\beta }\Longleftrightarrow v^{\alpha }=v^{\beta }$.

Proof

The ‘only if’ part. Suppose that $\text {Cay}(S,\rho )$ is $\text {ColAut}_\rho (S)$-vertex-transitive. Since $\text {ColAut}_\rho (S)\subseteq \text {ColEnd}_\rho (S)$, Lemma 4.1 applies, whence (i) follows. Since $\text {ColAut}_\rho (S)\subseteq \text {Aut}_\rho (S)$, Lemma 4.3 applies, whence (ii) follows. By Corollary 5.4, the action of $[\rho \rangle$ on S is left simple, whence (iii) follows. To show (iv), assume that $u^{\alpha }=u^{\beta }$ for any $u\in S$ and $\alpha , \beta \in [\rho \rangle$. Let $v\in S$. By the assumption that $\text {Cay}(S,\rho )$ is $\text {ColAut}_\rho (S)$-vertex-transitive, there exists $\phi \in \text {ColAut}_\rho (S)$ such that $\phi (u)=v$. By the definition of colure automorphisms, $\phi (u^\gamma )=(\phi (u))^\gamma$ for all $\gamma \in \rho$. This equation is easily extended to that for whole $[\rho \rangle$ by the definition of $[\rho \rangle$, that is, $\phi (u^\gamma )=(\phi (u))^\gamma$ for all $\gamma \in [\rho \rangle$. Consequently, $v^\alpha =(\phi (u))^\alpha =\phi (u^\alpha )=\phi (u^\beta )=(\phi (u))^\beta =v^\beta$. Therefore, (iv) follows.

The ‘if’ part. Suppose that conditions (i), (ii), (iii) and (iv) of Theorem 6.1 hold. Let $a,b\in S$. We want to find a mapping $\phi \in \text {ColAut}_\rho (S)$ such that $\phi (a)=b$.

According to Lemma 5.2, conditions (i) and (ii) of Theorem 6.1 imply that every connected component of $\text {Cay}(S,\rho )$ is strongly connected and that for every $u\in S$, $u\in C_u=u^{[\rho \rangle }$. It follows that connected components of $\text {Cay}(S,\rho )$ are precisely $C_u$’s for $u\in S$. Since $C_u=u^{[\rho \rangle }=u^{\alpha [\rho \rangle }$ and $\alpha [\rho \rangle$ with $\alpha \in [\rho \rangle$ is a finite set by the assumption of the theorem, we deduce that $C_u$ is also finite.

For any $u,v\in S$, we first define mappings $\psi _{u,v}$ and $\psi _{v,u}$ as follows:

$$\begin{aligned}&\psi _{u,v}:\quad C_u\longrightarrow C_v, \,\qquad u^\alpha \longmapsto v^\alpha ;\\&\psi _{v,u}:\quad C_v\longrightarrow C_u, \,\qquad v^\alpha \longmapsto u^\alpha . \end{aligned}$$

Condition (iv) of Theorem 6.1 ensures that both of $\psi _{u,v}$ and $\psi _{v,u}$ are well defined and mutually invertible mappings. Thus $|C_u|=|C_v|$ for all $u,v\in S$ and hence there exists a positive integer n such that $|C_u|=n$ for all $u\in S$.

Given $\alpha _0\in [\rho \rangle$, $C_a=a^{[\rho \rangle }=a^{\alpha _0[\rho \rangle }$. Thus we may assume that

$$\begin{aligned} C_a=\{a^{\alpha _0\beta _1}=a, a^{\alpha _0\beta _2},\ldots ,a^{\alpha _0\beta _n}\} \end{aligned}$$

for some $\beta _1,\ldots ,\beta _n\in [\rho \rangle$. Since $|C_b|=n$, condition (iv) of Theorem 6.1 implies that $C_b=\{b^{\alpha _0\beta _1}, b^{\alpha _0\beta _2},\ldots ,b^{\alpha _0\beta _n}\}$. Since $b\in C_b$, $b=b^{\alpha _0\beta _m}$ for some $m\le n$. By the condition (iii) of Theorem 6.1, $b^{[\rho \rangle }=b^{[\rho \rangle \beta _1}$. Whence $b^{\alpha _0\beta _m}=b^{\alpha _1\beta _1}$ for some $\alpha _1\in [\rho \rangle$. Hence condition (iv) of Theorem 6.1 implies that

$$\begin{aligned} C_b=\{b^{\alpha _1\beta _1}=b, b^{\alpha _1\beta _2},\ldots ,b^{\alpha _1\beta _n}\}. \end{aligned}$$

Now we can define mappings $\phi _{a,b}$ and $\phi _{b,a}$ as follows:

$$\begin{aligned} \phi _{a,b}=\psi _{a^{\alpha _0},b^{\alpha _1}}\, \text { and } \, \phi _{b,a}=\psi _{b^{\alpha _1},a^{\alpha _0}}. \end{aligned}$$

Then both of $\phi _{a,b}$ and $\phi _{b,a}$ are well defined and mutually invertible mappings such that $\phi _{a,b}(a)=b$ and $\phi _{b,a}(b)=a$. Consider two cases.

Case 1. $C_a=C_b$. For $x\in S$, we define

$$\begin{aligned} \phi (x) = \left\{ \begin{array}{ll} \phi _{a,b} (x) &{}\quad \text {if}\quad x\in C_a;\\ x &{}\quad \text {otherwise.} \end{array} \right. \end{aligned}$$

Then $\phi$ is well defined and is a bijection on S such that $\phi (a)=b$.

Let (u, v) be any edge of $\text {Cay}(S,\rho )$. Then $v=u^\alpha$ for some $\alpha \in \rho$. It follows that $C_u=C_v$. Suppose that $u\in C_a$. Then $C_u=C_v=C_a$. We may assume that $u=a^{\alpha _0\beta _s}$ and $v= a^{\alpha _0\beta _t}$ for some $s,t\le n$. Thus $a^{\alpha _0\beta _t}=v=u^\alpha =(a^{\alpha _0\beta _s})^\alpha =a^{\alpha _0\beta _s\alpha }$, which means that $b^{\alpha _1\beta _t}=b^{\alpha _1\beta _s\alpha }$. Hence $\phi (v)=\phi (a^{\alpha _0\beta _t})=b^{\alpha _1\beta _t}=b^{\alpha _1\beta _s\alpha }=(b^{\alpha _1\beta _s)^\alpha }=(\phi (a^{\alpha _0\beta _s}))^\alpha =(\phi (u))^\alpha$. If $u\in S\setminus C_a$, then so is v. Hence $\phi (v)=v=u^\alpha =(\phi (u))^\alpha$. Summing up, we have proved that $\phi (u^\alpha )=(\phi (u))^\alpha$. That is, $(\phi (u),\phi (v))$ is also an edge of $\text {Cay}(S,\rho )$. Hence $\phi \in \text {ColAut}_\rho (S)$, as desired.

Case 2. $C_a\ne C_b$. Then $C_a\cap C_b=\emptyset$. For $x\in S$, we define

$$\begin{aligned} \phi (x) = \left\{ \begin{array}{ll} \phi _{a,b} (x) &{}\quad \text {if} \quad x\in C_a;\\ \phi _{b,a} (x) &{}\quad \text {if}\quad x\in C_b;\\ x &{}\quad \text {otherwise.} \end{array} \right. \end{aligned}$$

Also, $\phi$ is well defined and is a bijection on S such that $\phi (a)=b$. Let (u, v) be any edge of $\text {Cay}(S,\rho )$. Then $v=u^\alpha$ for some $\alpha \in \rho$. It is readily verified that $\phi (u^\alpha )=(\phi (u))^\alpha$. That is, $(\phi (u),\phi (v))$ is also an edge of $\text {Cay}(S,\rho )$. Therefore, $\phi \in \text {ColAut}_\rho (S)$, which completes the proof. $\square$

Let T be an ideal extension of a semigroup S and $\rho$ a nonempty subset of $T^1\times T^1$. If A is a subset of S such that $A^{\rho }\subseteq A$, then the induced subgraph A of the generalized Cayley graph $\text {Cay}(S,\rho )$ is also denoted by $\text {Cay}(A,\rho )$. The automorphism group of $\text {Cay}(A,\rho )$ is also denoted by $\text {Aut}_\rho (A)$.

Theorem 6.2

Let T be an ideal extension of a semigroup S and $\rho$ a nonempty subset of $T^1\times T^1$ such that all principal right ideals of $[\rho \rangle$ are finite. Then, the generalized Cayley graph $\text {Cay}(S,\rho )$ is $\text {Aut}_\rho (S)$-vertex-transitive if and only if the following conditions hold:

• (i) $S^\rho =S$;

• (ii) the action of $[\rho \rangle$ on S is right simple;

• (iii) $\text {Cay}(a^{[\rho \rangle },\rho )$ is $\text {Aut}_\rho (a^{[\rho \rangle })$-vertex-transitive for some $a\in S$;

• (iv) for all $u,v\in S$, $\text {Cay}(u^{[\rho \rangle },\rho )\cong \text {Cay}(v^{[\rho \rangle },\rho )$.

Proof

The ‘only if’ part. Suppose that $\text {Cay}(S,\rho )$ is $\text {Aut}_\rho (S)$-vertex-transitive. Since $\text {Aut}_\rho (S)\subseteq \text {End}_\rho (S)$, Lemma 4.1 applies, whence (i) follows.

Since all principal right ideals of $[\rho \rangle$ are finite and the generalized Cayley graph $\text {Cay}(S,\rho )$ is $\text {Aut}_\rho (S)$-vertex-transitive, Corollary 5.3 applies, whence (ii) follows and furthermore, $C_u=u^{[\rho \rangle }=u^{\alpha [\rho \rangle }$ for each $u\in S$ and each $\alpha \in [\rho \rangle$. According to Lemma 5.2, every connected component of $\text {Cay}(S,\rho )$ is strongly connected and for every $u\in S$, $u\in C_u=u^{[\rho \rangle }$. It follows that connected components of $\text {Cay}(S,\rho )$ are precisely $C_u$’s for $u\in S$. Then the transitivity of $\text {Cay}(S,\rho )$ implies the transitivity of $\text {Cay}(a^{[\rho \rangle },\rho )$, i.e. (iii) of Theorem 6.2 follows.

For any $u\in S$ and $v\in S\setminus u^{[\rho \rangle }$, $C_u$ and $C_v$ are two different connected components. Then by the the transitivity of $\text {Cay}(S,\rho )$, there exists $\phi \in \text {Aut}_\rho (S)$ such that $\phi (u)=v$. Then the restriction of $\phi$ on the subgraph $C_u$ is an isomorphism from $C_u$ onto $C_v$. Hence $\text {Cay}(u^{[\rho \rangle },\rho )\cong \text {Cay}(v^{[\rho \rangle },\rho )$ and (iv) of Theorem 6.2 follows.

The ‘if’ part. Suppose that conditions (i), (ii), (iii) and (iv) of Theorem 6.2 hold. Let $a,b\in S$. We want to find a mapping $\phi \in \text {ColAut}_\rho (S)$ such that $\phi (a)=b$. According to Lemma 5.2, the conditions (i) and (ii) of Theorem 6.2 imply that every connected component of $\text {Cay}(S,\rho )$ is strongly connected and that for every $u\in S$, $u\in C_u=u^{[\rho \rangle }$. It follows that connected components of $\text {Cay}(S,\rho )$ are precisely $C_u=u^{[\rho \rangle }=u^{\alpha [\rho \rangle }$, where $u\in S$ and $\alpha \in [\rho \rangle$. Since $\alpha [\rho \rangle$ is a finite set, then so is $C_u$.

Consider two cases.

Case 1. $b\in v^{[\rho \rangle }$. Then $C_a=C_b$. Condition (iii) tells us that $\text {Cay}(C_a,\rho )$ is $\text {Aut}_\rho (C_a)$-vertex-transitive for some $a\in S$. Hence there exist $\phi _a\in \text {Aut}_\rho (C_a)$ such that $\phi _a(a)=b$. For $x\in S$, we define

$$\begin{aligned} \phi (x) = \left\{ \begin{array}{ll} \phi _a (x) &{} \quad \text {if }\quad x\in C_a;\\ x &{}\quad \text {otherwise.} \end{array} \right. \end{aligned}$$

Then $\phi$ is well defined and $\phi \in \text {Aut}_\rho (S)$ with $\phi (a)=b$.

Case 2. $b\in S\setminus a^{[\rho \rangle }$. $C_a$ and $C_b$ are vertex sets of two distinguished connected components of $\text {Cay}(S,\rho )$. Let $\psi _{a,b}$ be an isomorphism from $\text {Cay}(C_a,\rho )$ onto $\text {Cay}(C_b,\rho )$. Put $\psi _{b,a}=\psi _{a,b}^{-1}$. Then $\psi _{b,a}$ is an isomorphism from $\text {Cay}(C_b,\rho )$ onto $\text {Cay}(C_a,\rho )$. Put $c=\psi _{b,a}(b)$. Then $c\in C_a$; hence $C_a=C_c$. Condition (iii) of Theorem 6.2 tells us that $\text {Cay}(C_a,\rho )$ is $\text {Aut}_\rho (C_a)$-vertex-transitive. Thus $\psi (a)=c$ for some $\psi \in \text {Aut}_\rho (C_a)$. It is clear that the composition $(\psi _{a,b}\circ \psi )$ of $\psi$ and $\psi _{a,b}$ is also an isomorphism from $\text {Cay}(C_a,\rho )$ onto $\text {Cay}(C_b,\rho )$. In addition, $(\psi _{a,b}\circ \psi )(a)=\psi _{a,b}(\psi (a))=\psi _{a,b}(c)=b$.

For $x\in S$, we define

$$\begin{aligned} \phi (x) = \left\{ \begin{array}{ll} (\psi _{a,b}\circ \psi ) (x) &{}\quad \text {if}\quad x\in C_a;\\ \psi _{b,a} (x) &{}\quad \text {if}\quad x\in C_b;\\ x &{}\quad \text {otherwise.} \end{array} \right. \end{aligned}$$

Then $\phi$ is also well defined and $\phi \in \text {Aut}_\rho (S)$ with $\phi (a)=b$, which completes the proof. $\square$

7 Important corollaries

In this section, the main theorems of [10] are displayed and reproved as two corollaries of our main theorems.

Corollary 7.1

(Theorem 2.1 of [10]) Let G be a semigroup, and let S be a subset of G which generates a subsemigroup $\langle S\rangle$ such that all principal left ideals of $\langle S\rangle$ are finite. Then, the Cayley graph $\text {Cay}(G, S)$ is $\text {ColAut}_S(G)$-vertex-transitive if and only if the following conditions hold:

• (i) $sG = G$, for all $s \in S$;

• (ii) $\langle S\rangle$ is isomorphic to a direct product of a right zero band and a group;

• (iii) $|\langle S\rangle g|$ is independent of the choice of $g \in G$.

Proof

Notice that G can be regarded as an ideal extension of G itself. Let $\rho =S\times \{1\}\subseteq G\times G$. Then the condition that all principal left ideals of $\langle S\rangle$ are finite is equivalent to that all principal right ideals of $[\rho \rangle$ are finite, since every principal left ideal of $\langle S\rangle$ is precisely a principal right ideals of $[\rho \rangle$. In the current circumstance, we have $\text {Cay}(G, \rho )=\text {Cay}(G, S)$ and $\text {ColAut}_\rho (G)=\text {ColAut}_S(G)$. Hence the condition that the Cayley graph $\text {Cay}(G, S)$ is $\text {ColAut}_S(G)$-vertex-transitive is equivalent to that the generalized Cayley graph $\text {Cay}(S,\rho )$ is $\text {ColAut}_\rho (S)$-vertex-transitive.

The ‘only if’ part. Suppose that the Cayley graph $\text {Cay}(G, S)$ is $\text {ColAut}_S(G)$-vertex-transitive. Then the generalized Cayley graph $\text {Cay}(S,\rho )$ is $\text {ColAut}_\rho (S)$-vertex-transitive. According to Theorem 6.1, the results corresponding to conditions (i), (ii), (iii) and (iv) of Theorem 6.1 are valid.

Take any $s\in S$ and let $\alpha =(s, 1)$. Then by (i) of Theorem 6.1, $G^\alpha =G$, which means that $sG=G$. Thus (i) of Corollary 7.1 holds.

By (ii) of Theorem 6.1, the the action of $[\rho \rangle =\langle S\rangle \times \{1\}$ on G is right simple. Thus, for any $t\in \langle S\rangle$, $t^{\alpha [\rho \rangle }=t^{[\rho \rangle }$, that is, $\langle S\rangle st=\langle S\rangle t$. By Lemma 5.2, $t\in C_t=t^{[\rho \rangle }=\langle S\rangle t=\langle S\rangle st\subseteq \langle S\rangle s \langle S\rangle$. Since t was chosen arbitrarily, we have proved that $\langle S\rangle \subseteq \langle S\rangle s \langle S\rangle$. Thus, $\langle S\rangle = \langle S\rangle s \langle S\rangle$, which shows that $\langle S\rangle$ is a simple semigroup. By (iii) of Theorem 6.1, the the action of $[\rho \rangle$ on G is left simple. Thus, for any $t\in \langle S\rangle$, $t^{[\rho \rangle \alpha }=t^{[\rho \rangle }$. It follows that $\langle S\rangle t=s\langle S\rangle t$, which yields that $\langle S\rangle t\langle S\rangle =s\langle S\rangle t\langle S\rangle$. So, $\langle S\rangle =s\langle S\rangle$. Thus by Lemma 2.1, $\langle S\rangle$ is right simple. From the assumption that all principal left ideals of $\langle S\rangle$ are finite, it follows that $\langle S\rangle$ is a periodic semigroup. In view of Lemma 2.2, $\langle S\rangle$ is a right group and (ii) of Corollary 7.1 follows.

For any $u,v\in G$, as in the proof of Theorem 6.1, we define mappings $\psi _{u,v}$ and $\psi _{v,u}$ as follows:

$$\begin{aligned}&\psi _{u,v}:\quad C_u\longrightarrow C_v, \,\qquad u^\alpha \longmapsto v^\alpha ;\\&\psi _{v,u}:\quad C_v\longrightarrow C_u, \,\qquad v^\alpha \longmapsto u^\alpha . \end{aligned}$$

In light of (iv) of Theorem 6.1, we get that both of $\psi _{u,v}$ and $\psi _{v,u}$ are well defined and mutually invertible mappings. Thus $|C_u|=|C_v|$ for all $u,v\in G$. Consequently, $|\langle S\rangle g|$ is independent of the choice of $g \in G$, since $C_g=g^{[\rho \rangle }=\langle S\rangle g$. This proves (iii) of Corollary 7.1.

The ‘if’ part. Suppose that conditions (i), (ii), and (iii) of Corollary 7.1 hold. Take any $\alpha \in \rho$. Then there exists $s\in G$ such that $\alpha =(s,1)$. Then (i) of Corollary 7.1 yields $G^\alpha =G$, that is, condition (i) of Theorem 6.1 holds.

By Lemma 2.2 and condition (ii) of Corollary 7.1, $\langle S\rangle$ is a right group. It is a routine matter to check that $s\langle S\rangle =\langle S\rangle$ for all $s\in \langle S\rangle$ and that $\langle S\rangle st=\langle S\rangle t$ for all $s,t\in \langle S\rangle$. Now for any $\alpha \in [\rho \rangle$, there exists $s\in \langle S\rangle$ such that $\alpha =(s,1)$. For any $g\in G$, there exist $t\in \langle S\rangle$ and $h\in G$ such that $g=th$ by (i) of Corollary 7.1. Then $g^{\alpha [\rho \rangle }=\langle S\rangle sg=\langle S\rangle sth=\langle S\rangle th=\langle S\rangle g=g^{[\rho \rangle }$, which shows that the action of $[\rho \rangle$ on G is right simple; meanwhile, $g^{[\rho \rangle \alpha }=s\langle S\rangle g=\langle S\rangle g=g^{[\rho \rangle }$, which shows that the action of $[\rho \rangle$ on G is also left simple. Therefore, conditions (ii) and (iii) of Theorem 6.1 are satisfied.

For any $\alpha \in [\rho \rangle$, there exists $s\in \langle S\rangle$ such that $\alpha =(s,1)$. For any $g\in G$, $g^{\alpha [\rho \rangle }=\langle S\rangle th=\langle S\rangle g$ is a finite set. Since $\alpha [\rho \rangle =(s,1)(\langle S\rangle ,1)=(\langle S\rangle s,1)$, $|\alpha [\rho \rangle |=|(\langle S\rangle s,1)|=|\langle S\rangle s|$. Condition (iii) of Corollary 7.1 tells us that $|\langle S\rangle g|=|\langle S\rangle s|$. So, $|g^{\alpha [\rho \rangle }|=|\alpha [\rho \rangle |$, which is a finite number. Immediately, $\alpha [\rho \rangle \longrightarrow g^{\alpha [\rho \rangle }$, $\beta \longmapsto g^\beta$ is a bijection. Thus for any $\beta _1,\beta _2\in \alpha [\rho \rangle$, if $g^{\beta _1}=g^{\beta _2}$ then $\beta _1=\beta _2$. Suppose that $u,v\in G$ and $u^{\gamma _1}=u^{\gamma _2}$ with $\gamma _1,\gamma _2\in [\rho \rangle$. Then $u=g^\alpha$ and $v=h^\alpha$ for some $g,h\in G$ since $G^\alpha =G$. Thus $g^{\alpha \gamma _1}=u^{\gamma _1}=u^{\gamma _2}=g^{\alpha \gamma _2}$. Hence $\alpha \gamma _1=\alpha \gamma _2$, which yields that $v^{\gamma _1}=h^{\alpha \gamma _1}=h^{\alpha \gamma _2}=v^{\gamma _2}$. We have proved that $u^{\gamma _1}=u^{\gamma _2}$ implies $v^{\gamma _1}=v^{\gamma _2}$ for any $u,v\in G$ and any $\gamma _1,\gamma _2\in [\rho \rangle$. Therefore, (iv) of Theorem 6.1 follows. Applying Theorem 6.1, we obtain that the generalized Cayley graph $\text {Cay}(G,\rho )$ is $\text {ColAut}_\rho (G)$-vertex-transitive. In other words, the Cayley graph $\text {Cay}(G, S)$ is $\text {ColAut}_S(G)$-vertex-transitive. This completes the proof. $\square$

Corollary 7.2

(Theorem 2.2 of [10]) Let G be a semigroup, and let S be a subset of G which generates a subsemigroup $\langle S\rangle$ such that all principal left ideals of $\langle S\rangle$ are finite. Then, the Cayley graph $\text {Cay}(G, S)$ is $\text {Aut}_S(G)$-vertex-transitive if and only if the following conditions hold:

• (i) $SG =G$;

• (ii) $\langle S\rangle$ is a completely simple semigroup;

• (iii) the Cayley graph $Cay(\langle S\rangle , S)$ is $\text {Aut}_S(\langle S\rangle )$-vertex-transitive;

• (iv) $|\langle S\rangle g|$ is independent of the choice of $g \in G$.

Proof

Notice that G may be regarded as an ideal extension of G itself. Let $\rho =S\times \{1\}\subseteq G\times G$. Then the condition that all principal left ideals of $\langle S\rangle$ are finite is equivalent to that all principal right ideals of $[\rho \rangle$ are finite, since every principal left ideal of $\langle S\rangle$ is precisely a principal right ideals of $[\rho \rangle$. In the current circumstance, we have $\text {Cay}(G, S)=\text {Cay}(G, \rho )$ and $\text {Aut}_S(G)=\text {Aut}_\rho (G)$. Hence the condition that the Cayley graph $\text {Cay}(G, S)$ is $\text {Aut}_S(G)$-vertex-transitive is equivalent to that the generalized Cayley graph $\text {Cay}(S,\rho )$ is $\text {Aut}_\rho (S)$-vertex-transitive.

The ‘only if’ part. Suppose that the Cayley graph $\text {Cay}(G, S)$ is $\text {Aut}_S(G)$-vertex-transitive. Then the generalized Cayley graph $\text {Cay}(S,\rho )$ is $\text {Aut}_\rho (S)$-vertex-transitive. According to Theorem 6.2, the results corresponding to (i), (ii), (iii) and (iv) of Theorem 6.2 are valid.

Since $\rho =S\times \{1\}$ and by (i) of Theorem 6.2, $G^\rho =G$, which means that $SG=G$. Thus (i) of Corollary 7.2 holds.

By (ii) of Theorem 6.2, the the action of $[\rho \rangle =\langle S\rangle \times \{1\}$ on G is right simple. As in the proof of Corollary 7.1, by Lemma 5.2, we deduce that $\langle S\rangle$ is a simple semigroup. The assumption that all principal left ideals of $\langle S\rangle$ are finite implies that S is a periodic semigroup. Then by Lemma 2.4, $\langle S\rangle$ is a completely simple semigroup. Thus (ii) of Corollary 7.2 follows.

According to Lemma 5.2, the conditions (i) and (ii) of Theorem 6.2 imply that every connected component of $\text {Cay}(S,\rho )$ is strongly connected and that for every $u\in S$, $u\in C_u=u^{[\rho \rangle }$. It follows that connected components of $\text {Cay}(S,\rho )$ are precisely $C_u=u^{[\rho \rangle }=u^{\alpha [\rho \rangle }$, where $u\in S$ and $\alpha \in [\rho \rangle$. Conditions (iii) and (iv) of Theorem 6.2 imply that $\text {Cay}(g^{[\rho \rangle },\rho )\cong \text {Cay}(h^{[\rho \rangle },\rho )$ for all $g,h\in G$. Thus $|\langle S\rangle g|=|g^{[\rho \rangle }|=|h^{[\rho \rangle }|=|\langle S\rangle h|$ and (iv) of Corollary 7.2 follows. Furthermore, Noticing that $\langle S\rangle ^{\langle S\rangle }\subseteq [\rho \rangle$, $\langle S\rangle$ is a disjoint union of some connected components, we deduce that the Cayley graph $Cay(\langle S\rangle , S)$ is $\text {Aut}_S(\langle S\rangle )$-vertex-transitive. Thus statement (iii) of Corollary 7.2 holds.

The ‘if’ part. Suppose that conditions (i), (ii), (iii) and (iv) of Corollary 7.2 hold. Clearly, (i) of Corollary 7.2 yields $G^\rho =G$, that is, condition (i) of Theorem 6.2 holds.

By condition (ii) of Corollary 7.2, $\langle S\rangle$ is completely simple. So by Lemma 2.3, $\langle S\rangle$ is isomorphic to a Rees matrix semigroup ${\mathscr {M}}[H;I,\varLambda ; P]$ over a group H. We may assume that $\langle S\rangle ={\mathscr {M}}[H;I,\varLambda ; P]$ without loss of generality. It is a routine matter to check that $\langle S\rangle st=\langle S\rangle t$ for all $s,t\in \langle S\rangle$. Now for any $\alpha \in [\rho \rangle$, there exists $s\in \langle S\rangle$ such that $\alpha =(s,1)$. For any $g\in G$, there exist $t\in \langle S\rangle$ and $h\in G$ such that $g=th$ by (i) of Corollary 7.2. Then $g^{\alpha [\rho \rangle }=\langle S\rangle sg=\langle S\rangle sth=\langle S\rangle th=\langle S\rangle g=g^{[\rho \rangle }$, which shows that the action of $[\rho \rangle$ on G is right simple. Therefore, conditions (ii) of Theorem 6.2 is satisfied.

For some $a\in S$, $a^{[\rho \rangle }\subseteq \langle S\rangle$. Since the Cayley graph $Cay(\langle S\rangle , S)$ is $\text {Aut}_S(\langle S\rangle )$-vertex-transitive by (iii) of Corollary 7.2, $\text {Cay}(a^{[\rho \rangle },\rho )$ is $\text {Aut}_\rho (a^{[\rho \rangle })$-vertex-transitive. Thus (iii) of Theorem 6.2 holds.

For any $\alpha \in [\rho \rangle$, there exists $s\in \langle S\rangle$ such that $\alpha =(s,1)$. For any $g\in G$, $g^{\alpha [\rho \rangle }=\langle S\rangle th=\langle S\rangle g$ is a finite set. Since $\alpha [\rho \rangle =(s,1)(\langle S\rangle ,1)=(\langle S\rangle s,1)$, $|\alpha [\rho \rangle |=|(\langle S\rangle s,1)|=|\langle S\rangle s|$. Condition (iv) of Corollary 7.2 tells us that $|\langle S\rangle g|=|\langle S\rangle s|$. So, $|g^{\alpha [\rho \rangle }|=|\alpha [\rho \rangle |$, which is a finite number. Immediately, $\alpha [\rho \rangle \longrightarrow g^{\alpha [\rho \rangle }$, $\beta \longmapsto g^\beta$ is a bijection. Thus for any $\beta _1,\beta _2\in \alpha [\rho \rangle$, if $g^{\beta _1}=g^{\beta _2}$ then $\beta _1=\beta _2$.

For any $u,v\in G$, as in the proof of Theorem 6.1, we define mappings $\psi _{u,v}$ and $\psi _{v,u}$ as follows:

$$\begin{aligned}&\psi _{u,v}:\quad C_u\longrightarrow C_v, \,\qquad u^{\alpha \beta }\longmapsto v^{\alpha \beta };\\&\psi _{v,u}:\quad C_v\longrightarrow C_u, \,\qquad v^{\alpha \beta }\longmapsto u^{\alpha \beta }. \end{aligned}$$

Then both of $\psi _{u,v}$ and $\psi _{v,u}$ are well defined and mutually invertible mappings. Moreover, $\psi _{u,v}$ is an isomorphism from $\text {Cay}(u^{[\rho \rangle },\rho )$ onto $\text {Cay}(v^{[\rho \rangle },\rho )$. Thus $\text {Cay}(u^{[\rho \rangle },\rho )\cong \text {Cay}(v^{[\rho \rangle },\rho )$, that is, condition (iv) of Theorem 6.2 is satisfied.

Applying Theorem 6.2, we obtain that the generalized Cayley graph $\text {Cay}(G,\rho )$ is $\text {Aut}_\rho (G)$-vertex-transitive. In other words, the Cayley graph $\text {Cay}(G, S)$ is $\text {Aut}_S(G)$-vertex-transitive. This completes the proof. $\square$

8 An example

Let us conclude this paper with the following example, which shows more extensive applications of our main theorems.

Example 8.1

Let A, B be two subgroups of a finite group S with $(|A|,|B|)=1$, and let $\rho =A\times B$. Then $[\rho \rangle =A^*\times B$. Take any $u\in G$. We have $u^{[\rho \rangle }=A^*uB$. Because $(|A|,|B|)=1$, we have

$$\begin{aligned} |u^{[\rho \rangle }| = |A^*uB| = |u^{-1}A^*uB| = |(A^*)^uB| = \frac{ |(A^*)^u||B|}{ |(A^*)^u\cap B|}= |(A^*)^u||B|=|A||B|, \end{aligned}$$

where $(A^*)^u=u^{-1}A^*u;$ On the other hand, since $[\rho \rangle$ is also a group, we have

$$\begin{aligned} |[\rho \rangle |=|A^*||B|=|A||B|. \end{aligned}$$

So,

$$\begin{aligned} |u^{[\rho \rangle }| =|[\rho \rangle |. \end{aligned}$$

The finiteness condition ensures that the map $\phi$: $[\rho \rangle \longrightarrow u^{[\rho \rangle }$, $\alpha \longrightarrow u^\alpha$ is a bijection. It follows that for any $u,v\in S$ and $\alpha ,\beta \in [\rho \rangle$, $u^{\alpha }=u^{\beta }\Longleftrightarrow v^{\alpha }=v^{\beta }$. This shows that condition (iv) of Theorem 6.1 is satisfied. It is easy to check that conditions (i), (ii) and (iii) of Theorem 6.1 are also satisfied. According to Theorem 6.1, the generalized Cayley graph $\text {Cay}(S,\rho )$ is $\text {ColAut}_\rho (S)$-vertex-transitive. Since trivially, $\text {ColAut}\rho (S))\subseteq \text {Aut}\rho (S)$, the generalized Cayley graph $\text {Cay}(S,\rho )$ is also $\text {Aut}\rho (S)$-vertex-transitive. So the four conditions of Theorem 6.2 are all satisfied.