Certain structural properties for Cayley regularity graphs of semigroups and their theoretical applications

1.   Introduction

The study of graphs in connection to an algebraic system is a branch of algebraic graph theory. Some properties in the algebraic system will be applied for determining properties of graphs induced by the algebraic system. One of several graphs induced from algebraic systems is the Cayley graph which was introduced by Arthur Cayley in 1878. This concept was considered to interpret the structures of abstract groups which are expressed as the set of group generators and then applied to problems about graphs. Furthermore, the construction of Cayley graphs is also applied to semigroups. As the fact that Cayley graphs of semigroups can reflect the structural properties of semigroups, such semigroups can be visualized by constructing their Cayley graphs. To prescribe the definition of Cayley graphs, let $S$ be a semigroup and $A$ a subset of $S$. The Cayley graph $\text{Cay}(S, A)$ of a semigroup $S$ with respect to the set $A$ is defined to be a digraph with vertex set $S$ and arc set containing all ordered pairs $(x, xa)$ for some $a\in A$ and $x$ is an arbitrary element in $S$. We call $A$ a connection set of $\text{Cay}(S, A)$. It is easily visible that if $A$ is an empty set, then $\text{Cay}(S, A)$ is considered to be an empty graph. In order to present another new relation between algebra and graph theory, we construct the Cayley regularity graph $\text{CR}(S)$ of a semigroup $S$ which is a digraph whose vertex set is the semigroup $S$ and arc set is the set of all ordered pairs $(x, y)$, where $x, y\in S$, such that $y$ is the regular part of $x$, that is, $x = xyx$. In addition, we generally study the structural properties consisting of connectedness and completeness of $\text{CR}(S)$. Furthermore, the equivalence digraph properties of $\text{CR}(S)$ are also completely investigated.

Recently, the Cayley graphs of semigroups were widely studied and they have received serious attention in the literature. In order to apply the connection between graph theory and semigroup theory, a lot of work has been done on the study of Cayley graphs of semigroups with respect to their graph theoretical properties. Many results of Cayley graphs of particular types of semigroups have been investigated. In 2006, Kelarev ^[1] described all inverse semigroups with Cayley graphs which are disjoint unions of complete graphs. In 2007, Fan and Zeng ^[2] obtained a complete description of all vertex-transitive Cayley graphs of bands. Later in 2010, Hao and Luo ^[3] investigated the basic structures and properties of Cayley graphs of left groups and right groups. In the same year, Khosravi and Mahmoudi ^[4] characterized the Cayley graphs of rectangular groups and studied their vertex-transitivity. Further in 2011, Luo, Hao, and Clarke ^[5] considered Cayley graphs of completely simple semigroups. In addition, they studied some structural properties such as completeness and strongly connected bipartite Cayley graphs. Indeed, it turns out that Cayley graphs of semigroups are significant not only in semigroup theory, but also in constructions of various interesting types of graphs with nice combinatorial properties. Several algebraic properties of those graph constructions have been presented in numerous journals (see for example, ^[6,7,8]).

In this part, other basic preliminaries and relevant notations about digraphs, semigroups and Cayley graphs of semigroups are described. Moreover, we are willing to refer to ^[9] for more information about digraphs, and ^[10,11,12] for others on semigroups. All sets mentioned in this research are assumed to be finite. A digraph $D$ (directed graph) is a pair $(V(D), E(D))$ where $V(D)$ is a nonempty set, called a vertex set, whose elements are called vertices and $E(D)$ is the subset of the set of ordered pairs of elements of $V(D)$. In other words, the set $E(D)$ can be considered as a relation on the set $V(D)$. The elements of $E(D)$ are called the arcs of $D$ and $E(D)$ is called an arc set. Furthermore, an arc of the form $(u, u)$ is called a loop of $D$. A digraph $D$ is called a complete digraph if for each $u, v\in V(D)$, $(u, v)\in E(D)$. Moreover, the digraph $D$ is said to be semi-complete if for every $u, v\in V(D)$, $(u, v)\in E(D)$ or $(v, u)\in E(D)$. Furthermore, $D$ is said to be directed complete if, for every $u, v\in V(D)$ with $u\neq v$, either $(u, v)\in E(D)$ or $(v, u)\in E(D)$.

Let $D$ be a digraph. Consider a sequence $P: = v_1, v_2, \ldots, v_k$ of distinct vertices in $V(D)$. If $P$ satisfies the condition that $(v_i, v_{i+1})\in E(D)$ or $(v_{i+1}, v_i)\in E(D)$ for all $i = 1, 2, \ldots, k-1$, then $P$ is said to be a semidipath from $v_1$ to $v_k$ in $D$. Moreover, if $P$ satisfies that $(v_i, v_{i+1})\in E(D)$ for all $i = 1, 2, \ldots, k-1$, then $P$ is said to be a dipath from $v_1$ to $v_k$ in $D$. For convenience, throughout this paper, the notation $[u, v]$-semidipath ($[u, v]$-dipath) stands for the semidipath (dipath) from $u$ to $v$. For any two distinct vertices $u$ and $v$ in $V(D)$, a digraph $D$ is said to be strongly connected if an $[u, v]$-dipath exists in $D$. Moreover, the digraph $D$ is said to be weakly connected if an $[u, v]$-semidipath exists in $D$. The digraph $D$ is said to be locally connected whenever an $[u, v]$-dipath exists in $D$, a $[v, u]$-dipath must exist in $D$ as well. In addition, $D$ is said to be unilaterally connected if an $[u, v]$-dipath or a $[v, u]$-dipath exists in $D$. A digraph $D$ is called an equivalence digraph if $E(D)$ is an equivalence relation on the set $V(D)$.

Example 1.1. Take $S_1 = \{a, b, c\}$, $S_2 = \{d, e, f\}$, $S_3 = \{g, h, i, j\}$, $S_4 = \{l, m, n\}$, $S_5 = \{o, p, q\}$ with the defining multiplications $*_1, *_2, *_3, *_4, *_5$ as shown in Figure 1. Then $(S_1, *_1), (S_2, *_2), (S_3, *_3), (S_4, *_4), (S_5, *_5)$ are semigroups and we get the Cayley regularity graphs of $S_1, S_2, S_3, S_4, S_5$ as indicated in Figure 1.

From Example 1.1, we observe that:

Thus in this research, we shall investigate connectedness and completeness of Cayley regularity graphs of semigroups. We determine conditions of semigroups that Cayley regularity graphs satisfy the property of being strongly connected, weakly connected, locally connected, unilaterally connected, complete, semi-complete, directed complete, and equivalence digraphs. Moreover, we apply structural properties of the Cayley regularity graphs to study perfect matchings of commuting graphs of groups.

2.   Connectedness and completeness of ${\text{CR}}(S)$

In this section, we investigate a class of connectedness and a class of completeness for Cayley regularity graphs of semigroups. Recall that $\text{CR}(S)$ denotes the Cayley regularity graph of a semigroup $S$ with vertex set $V(\text{CR}(S)) = S$ and arc set $E(\text{CR}(S)) = \{(x, y)\in S\times S\, :\, x = xyx\}$. For each element $s$ in a semigroup $S$, we define

First, we consider a condition of semigroups that Cayley regularity graphs are strongly connected.

Theorem 2.1. Let $S$ be a semigroup. Then $\mathit{{CR}}(S)$ is strongly connected if and only if each couple of vertices $x, y$ of $\mathit{{CR}}(S)$ satisfies the condition that there exist $x_0, x_1, x_2, \ldots, x_k\in S$ such that $x_0 = x$, $x_k = y$ and $x_i\in R^{+}(x_{i-1})$ for all $1\leq i\leq k$.

Proof. Assume that $\text{CR}(S)$ is strongly connected. We first prove the necessary condition. Let $x, y\in S$. By the strongly connectedness of $\text{CR}(S)$, there exists a dipath joining from $x$ to $y$, say $P$. Hence $P$ can be expressed as a sequence of vertices $x_0, x_1, x_2, \ldots, x_{k-1}, x_k$ where $x_0 = x$ and $x_k = y$ for some $x_1, x_2, \ldots, x_{k-1}\in S$. For each $i\in \{1, 2, \ldots, k\}$, we obtain $(x_{i-1}, x_i)\in E(\text{CR}(S))$. That means $x_{i-1} = x_{i-1}x_ix_{i-1}$ which implies $x_i\in R^{+}(x_{i-1})$, as required.

Conversely, assume that the condition holds. Let $x, y$ be vertices of $\text{CR}(S)$. By our assumption, there exist $x_0, x_1, x_2, \ldots, x_k\in S$ such that $x_0 = x$, $x_k = y$ and $x_i\in R^{+}(x_{i-1})$ for all $1, 2, \ldots, k$. Thus $x_{i-1} = x_{i-1}x_ix_{i-1}$, that is, $(x_{i-1}, x_i)\in E(\text{CR}(S))$ for all $1, 2, \ldots, k$. Therefore, $x_0, x_1, x_2, \ldots, x_{k-1}, x_k$ is an $[x, y]$-dipath in $\text{CR}(S)$ which yields that $\text{CR}(S)$ is strongly connected. This completes the proof.

□

Consider the strongly connected digraph $\text{CR}(S_1)$ in Example 1.1. We see at once that $\text{CR}(S_1)$ contains a cycle $abca$ such that $b\in R^{+}(a), c\in R^{+}(b)$ and $a\in R^{+}(c)$. It follows that each couple of vertices in $\text{CR}(S_1)$ satisfies the condition in Theorem 2.1.

From Example 1.1, we see that $\text{CR}(S_2)$ is weakly connected, but not unilaterally connected. The next theorem gives a condition of semigroups that Cayley regularity graphs are weakly connected.

Theorem 2.2. Let $S$ be a semigroup. Then $\mathit{{CR}}(S)$ is weakly connected if and only if each couple of vertices $x, y$ of $\mathit{{CR}}(S)$ satisfies the condition that there exist $x_0, x_1, x_2, \ldots, x_k\in S$ where $x_0 = x$ and $x_k = y$ such that $x_i\in R^{+}(x_{i-1})$ or $x_i\in R^{-}(x_{i-1})$ for all $1\leq i\leq k$.

Proof. Assume that $\text{CR}(S)$ is weakly connected. Let $x, y\in S$. By the weakly connectedness of $\text{CR}(S)$, there exists a semidipath joining between $x$ and $y$. Let the $[x, y]$-semidipath, say $P$, be expressed as a sequence of vertices $x_0, x_1, x_2, \ldots, x_k\in S$ where $x_0 = x$ and $x_k = y$ such that either $(x_{i-1}, x_i)\in E(\text{CR}(S))$ or $(x_{i}, x_{i-1})\in E(\text{CR}(S))$ for all $i = 1, 2, \ldots, k$. Hence $x_{i-1} = x_{i-1}x_ix_{i-1}$ or $x_{i} = x_{i}x_{i-1}x_{i}$, that means $x_i\in R^{+}(x_{i-1})$ or $x_i\in R^{-}(x_{i-1})$ for all $1\leq i\leq k$.

Conversely, assume that the condition holds. Let $x, y$ be two vertices of $\text{CR}(S)$. By the assumption, there exists $x_0, x_1, x_2, \ldots, x_k\in S$ where $x_0 = x$ and $x_k = y$ such that $x_i\in R^{+}(x_{i-1})$ or $x_i\in R^{-}(x_{i-1})$ for all $i = 1, 2, \ldots, k$. We obtain $x_{i-1} = x_{i-1}x_ix_{i-1}$ or $x_{i} = x_{i}x_{i-1}x_{i}$ for all $i = 1, 2, \ldots, k$, that is, $(x_{i-1}, x_i)\in E(\text{CR}(S))$ or $(x_{i}, x_{i-1})\in E(\text{CR}(S))$. Thus $\text{CR}(S)$ contains a semidipath joining between $x$ and $y$. Consequently, $\text{CR}(S)$ is a weakly connected digraph.

□

Consider the weakly connected digraph $\text{CR}(S_2)$ again. We see that $\text{CR}(S_2)$ contains a semidipath $dfe$ such that $f\in R^{-}(e)$ and $e\in R^{+}(f)$. It follows that each couple of vertices in $\text{CR}(S_2)$ satisfies the condition in Theorem 2.2.

We also see that, in Example 1.1, $\text{CR}(S_3)$ is locally connected, but not weakly connected. In the next theorem, we give a condition of semigroups that Cayley regularity graphs are locally connected.

Theorem 2.3. Let $S$ be a semigroup. Then $\mathit{{CR}}(S)$ is locally connected if and only if each couple of vertices $x, y$ of $\mathit{{CR}}(S)$ satisfies the condition that if there exist $x_0, x_1, x_2, \ldots, x_k\in S$ where $x_0 = x$ and $x_k = y$ such that $x_i\in R^{+}(x_{i-1})$ for all $i = 1, 2, \ldots, k$, then there exist $y_0, y_1, y_2, \ldots, y_l\in S$ where $y_0 = y$ and $y_l = x$ such that $y_j\in R^{+}(y_{j-1})$ for all $j = 1, 2, \ldots, l$.

Proof. Let $S$ be a semigroup. To prove the necessity, assume that $\text{CR}(S)$ is locally connected. Let $x, y\in S$ be such that there exist $x_0, x_1, x_2, \ldots, x_k\in S$ where $x_0 = x$ and $x_k = y$ such that $x_i\in R^{+}(x_{i-1})$ for all $i = 1, 2, \ldots, k$. It follows that $x_{i-1} = x_{i-1}x_ix_{i-1}$ which leads to $(x_{i-1}, x_i)\in E(\text{CR}(S))$ for all $i = 1, 2, \ldots, k$. We thus get $x_0, x_1, x_2, \ldots, x_{k-1}, x_k$ is an $[x, y]$-dipath in $\text{CR}(S)$. As a result of the locally connectedness of $\text{CR}(S)$, there exists a $[y, x]$-dipath in $\text{CR}(S)$. Assume that such the $[y, x]$-dipath is denoted by $P$. Hence $P$ can be written as a sequence of vertices $y_0, y_1, y_2, \ldots, y_{l-1}, y_l$ where $y_0 = y$ and $y_l = x$ for some $y_0, y_1, y_2, \ldots, y_{l-1}\in S$ and $(y_{j-1}, y_j)\in E(\text{CR}(S))$ for all $j = 1, 2, \ldots, l$. Thus $y_{j-1} = y_{j-1}y_jy_{j-1}$ which means $y_j\in R^{+}(y_{j-1})$ for all $j = 1, 2, \ldots, l$.

For proving the sufficiency, assume that the condition holds. Let $x, y\in S$. Suppose that there exists an $[x, y]$-dipath in $\text{CR}(S)$, say $T$. Hence there exist $x_1, x_2, \ldots, x_{k-1}\in S$ such that they form the dipath $T$ as $x_0, x_1, x_2, \ldots, x_{k-1}, x_k$ where $x_0 = x$ and $x_k = y$ in which $(x_{i-1}, x_i)\in E(\text{CR}(S))$ for all $i = 1, 2, \ldots, k$. It implies that $x_i\in R^{+}(x_{i-1})$ for all $i = 1, 2, \ldots, k$. By the assumption, there exist $y_0, y_1, y_2, \ldots, y_l\in S$ where $y_0 = y$ and $y_l = x$ such that $y_j\in R^{+}(y_{j-1})$ for all $j = 1, 2, \ldots, l$. Then $y_{j-1} = y_{j-1}y_jy_{j-1}$ which leads to $(y_{j-1}, y_j)\in E(\text{CR}(S))$ for all $j = 1, 2, \ldots, l$. We can conclude that $\text{CR}(S)$ contains a $[y, x]$-dipath. Consequently, $\text{CR}(S)$ is a locally connected digraph.

□

We now turn to consider the locally connected digraph $\text{CR}(S_3)$. It is easily seen that $\text{CR}(S_3)$ has two components. The first component contains a cycle $gig$ such that $i\in R^{+}(g)$ and $g\in R^{+}(i)$. The second component contains a cycle $hjh$ such that $h\in R^{+}(j)$ and $j\in R^{+}(h)$. It follows that each couple of vertices in $\text{CR}(S_3)$ satisfies the condition in Theorem 2.3.

In Example 1.1, we see that $\text{CR}(S_4)$ is unilaterally connected, but not locally connected and strongly connected. We now present a condition of semigroups that Cayley regularity graphs are unilaterally connected.

Theorem 2.4. Let $S$ be a semigroup. Then $\mathit{{CR}}(S)$ is unilaterally connected if and only if each couple of vertices $x, y$ of $\mathit{{CR}}(S)$ satisfies the condition that there exist $x_0, x_1, x_2, \ldots, x_k\in S$ where $x_0 = x$ and $x_k = y$ such that $x_i\in R^{+}(x_{i-1})$ for all $1\leq i\leq k$ or $x_{i-1}\in R^{+}(x_{i})$ for all $1\leq i\leq k$.

Proof. Assume that $\text{CR}(S)$ is unilaterally connected. Let $x, y\in S$. Since $\text{CR}(S)$ is unilaterally connected, there exists a dipath joining from $x$ to $y$ or from $y$ to $x$. If we let $P_1$ be the $[x, y]$-dipath, then $P_1$ can be written as a sequence $x_0, x_1, x_2, \ldots, x_{k-1}, x_k$ with $x_0 = x$ and $x_k = y$ for some $x_1, x_2, \ldots, x_{k-1}\in S$. Hence $(x_{i-1}, x_i)\in E(\text{CR}(S))$ for all $i = 1, 2, \ldots, k$. Thus $x_{i-1} = x_{i-1}x_ix_{i-1}$ which leads to $x_i\in R^{+}(x_{i-1})$ for all $i = 1, 2, \ldots, k$. Further, if $P_2$ is the $[y, x]$-dipath, then we can obtain, similarly to the above argument, that there exist $x_0, x_1, x_2, \ldots, x_k\in S$ where $x_0 = x$ and $x_k = y$ in which $x_{i-1}\in R^{+}(x_{i})$ for all $i = 1, 2, \ldots, k$.

In order to prove the converse, we assume that the condition holds. Let $x, y\in S$. By our assumption, there exist $x_0, x_1, x_2, \ldots, x_k\in S$ where $x_0 = x$ and $x_k = y$ such that $x_i\in R^{+}(x_{i-1})$ for all $1\leq i\leq k$ or $x_{i-1}\in R^{+}(x_{i})$ for all $1\leq i\leq k$. It is not hard to verify that there exists an $[x, y]$-dipath or a $[y, x]$-dipath in $\text{CR}(S)$. Therefore $\text{CR}(S)$ is unilaterally connected, as desired.

□

We now consider the unilaterally connected digraph $\text{CR}(S_4)$ again. We see that $\text{CR}(S_4)$ contains a dipath $nml$ such that $m\in R^{+}(n)$ and $l\in R^{+}(m)$. It follows that each couple of vertices in $\text{CR}(S_4)$ satisfies the condition in Theorem 2.4.

The characterizations for various types of completeness of $\text{CR}(S)$ are presented as follows. We first present a condition of semigroups that Cayley regularity graphs satisfy the property of completeness.

Theorem 2.5. Let $S$ be a semigroup. Then $\mathit{{CR}}(S)$ is complete if and only if $R^{+}(s) = S$ for all $s\in S$.

Proof. Let $\text{CR}(S)$ be a complete digraph. Further, let $s\in S$. Clearly, $R^{+}(s)\subseteq S$. Let $t\in S$. By the completeness of $\text{CR}(S)$, $(s, t)\in E(\text{CR}(S))$. Then $s = sts$ which implies that $t\in R^{+}(s)$. Therefore, $R^{+}(s) = S$.

Conversely, assume that $R^{+}(s) = S$ for all $s\in S$. Let $u, v\in S$. We have $v\in S = R^{+}(u)$. This implies that $u = uvu$ and hence $(u, v)\in E(\text{CR}(S))$. We consequently conclude that $\text{CR}(S)$ is a complete digraph.

□

Consider the complete digraph $\text{CR}(S_1)$ in Example 1.1. By the definition of $*_1$, we have $R^{+}(a) = R^{+}(b) = R^{+}(c) = S_1$. It follows that the condition of Theorem 2.5 is satisfied.

In Example 1.1, we see that $\text{CR}(S_5)$ is semi-complete, but not complete and directed complete. We now give a condition of semigroups that Cayley regularity graphs are semi-complete.

Theorem 2.6. Let $S$ be a semigroup. Then $\mathit{{CR}}(S)$ is semi-complete if and only if $R^{+}(s)\cup R^{-}(s) = S$ for all $s\in S$.

Proof. Let $\text{CR}(S)$ be semi-complete and let $s\in S$. We only need to prove that $S$ is contained in $R^{+}(s)\cup R^{-}(s)$. Let $t\in S$. Since $\text{CR}(S)$ is semi-complete, we have $(s, t)\in E(\text{CR}(S))$ or $(t, s)\in E(\text{CR}(S))$. If $(s, t)\in E(\text{CR}(S))$, then $s = sts$ which implies that $t\in R^{+}(s)$. Similarly, we get $t\in R^{-}(s)$ in the case where $(t, s)\in E(\text{CR}(S))$. This yields that $S = R^{+}(s)\cup R^{-}(s)$.

Conversely, assume that $R^{+}(s)\cup R^{-}(s) = S$ for all $s\in S$. Let $u, v\in S$. Hence $v\in R^{+}(s)\cup R^{-}(s)$. If $v\in R^{+}(u)$, then $u = uvu$ and thus $(u, v)\in E(\text{CR}(S))$. If $v\in R^{-}(u)$, then $v = vuv$ which implies that $(v, u)\in E(\text{CR}(S))$. Therefore $\text{CR}(S)$ is semi-complete which completely proves the assertion.

□

We now turn to consider the semi-complete digraph $\text{CR}(S_5)$. By the definition of $*_5$, we have $R^{+}(o) = \{o, p\}, R^{-}(o) = \{o, p, q\}, R^{+}(p) = \{o, p\}, R^{-}(p) = \{o, p, q\}, R^{+}(q) = \{o, p, q\}$ and $R^{-}(q) = \{q\}$. It follows that the condition of Theorem 2.6 is satisfied.

From Example 1.1, we also see that $\text{CR}(S_4)$ is directed complete, but not semi-complete. In the next theorem, we present a condition of semigroups that Cayley regularity graphs are directed complete.

Theorem 2.7. Let $S$ be a semigroup. Then $\mathit{{CR}}(S)$ is directed complete if and only if $S\setminus\{s\}$ is the disjoint union of $R^{+}(s)\setminus\{s\}$ and $R^{-}(s) \setminus\{s\}$ for all $s\in S$.

Proof. Let $\text{CR}(S)$ be directed complete and let $s\in S$. We first show that $S\setminus\{s\}$ is contained in $R^{+}(s)\cup R^{-}(s)$. Let $t\in S\setminus\{s\}$. Then $t\neq s$. Since $\text{CR}(S)$ is directed complete, we obtain either $(s, t)\in E(\text{CR}(S))$ or $(t, s)\in E(\text{CR}(S))$. If $(s, t)\in E(\text{CR}(S))$, then $s = sts$ which implies that $t\in R^{+}(s)\setminus\{s\}$. Similarly, we can observe that $t\in R^{-}(s)\setminus\{s\}$ whether $(t, s)\in E(\text{CR}(S))$. Consequently, $S\setminus\{s\} = (R^{+}(s)\setminus\{s\})\cup (R^{-}(s)\setminus\{s\})$. Next, we will prove that the sets $R^{+}(s)\setminus\{s\}$ and $R^{-}(s)\setminus\{s\}$ are disjoint. We now suppose to the contrary that there exists $x\in (R^{+}(s)\setminus\{s\})\cap (R^{-}(s)\setminus\{s\})$. Thus $s = sxs$ and $x = xsx$ which imply that $(s, x)\in E(\text{CR}(S))$ and $(x, s)\in E(\text{CR}(S))$. This contradicts to the directed completeness of $\text{CR}(S)$ since every pair of distinct vertices $u$ and $v$ in $\text{CR}(S)$ must be joined by only one directed edge. Therefore $R^{+}(s)\setminus\{s\}$ and $R^{-}(s)\setminus\{s\}$ are mutually disjoint.

Conversely, assume that the condition holds. We will investigate that $\text{CR}(S)$ is directed complete. Let $x, y$ be two distinct vertices of $\text{CR}(S)$. Suppose that $(y, x)\notin E(\text{CR}(S))$. Then $y\notin R^{-}(x)$ and so $y\notin R^{-}(x)\setminus\{x\}$. From $y\neq x$ and by the assumption, we have $y\in R^{+}(x)\setminus\{x\}$. That means $(x, y)\in E(\text{CR}(S))$. Moreover, we can observe that both of $(x, y)$ and $(y, x)$ can not lie in $E(\text{CR}(S))$ at the same time. As the result of $(x, y), (y, x)\in E(\text{CR}(S))$, it implies that $y\in (R^{+}(x)\setminus\{x\})\cap (R^{-}(x)\setminus\{x\})$ which contradicts to the assumption. Accordingly, the assertion is completely proved.

□

We now consider the directed complete digraph $\text{CR}(S_4)$ again. By the definition of $*_4$, we get $R^{+}(l)\setminus\{l\} = \emptyset, R^{-}(l)\setminus\{l\} = \{m, n\}, R^{+}(m)\setminus\{m\} = \{l\}, R^{-}(m)\setminus\{m\} = \{n\}, R^{+}(n)\setminus\{n\} = \{l, m\}$ and $R^{-}(n)\setminus\{n\} = \emptyset$. It follows that the condition of Theorem 2.7 is satisfied.

3.   Equivalence digraphs ${\text{CR}}(S)$

This section provides some characterizations of equivalence digraphs $\text{CR}(S)$. We first need to prescribe some terminologies as follows. A digraph $D' = (V', E')$ is said to be a subdigraph of a digraph $D = (V, E)$ if $V' \subseteq V$ and $E' \subseteq E$. Moreover, for any nonempty subset $W$ of $V$, a subdigraph of $D$ induced by $W$ called an induced subdigraph, which is denoted by $[W]$, is a subdigraph of $D$ satisfying the condition that if $u, v \in W$ and $(u, v) \in E$, then $(u, v)$ is an arc of $[W]$, as well. In addition, let $S$ be a semigroup. A nonempty subset $A$ of $S$ is said to be perfect regular if $x = xyx$ for all $x, y\in A$. Furthermore, let $k\in \mathbb{N}$ and $\mathcal{P}: = \{P_1, P_2, \ldots, P_k\}$ be a partition of $S$. For the Cayley regularity graph $\text{CR}(S)$, the partition $\mathcal{P}$ is said to be well-turned if induced subdigraphs $[P_1], [P_2], \ldots, [P_k]$ are maximal weakly connected subdigraphs of $\text{CR}(S)$.

Theorem 3.1. Let $S$ be a semigroup. The following conditions are equivalent.

(1) $\mathit{{CR}}(S)$ is an equivalence digraph.

(2) $\mathit{{CR}}(S)$ is the disjoint union of complete subdigraphs.

(3) $S$ can be partitioned into its disjoint subsets which each of them is perfect regular and this partition is well-turned.

Proof. $(1)\Rightarrow (2) :$ Let $\text{CR}(S)$ be an equivalence digraph. Then $E(\text{CR}(S))$ is an equivalence relation on $S$. For convenience, we denote by $E$ the arc set $E(\text{CR}(S))$. We will use the symbol $S/_E$ to denote the quotient set of $S$ by the equivalence relation on $S$ induced by the edge set $E$. It follows that $S/_E$ forms a partition of $S$. We may assume that $S/_E = \{A_1, A_2, \ldots, A_k\}$ for some $k\in\mathbb{N}$.

Firstly, we will show that subdigraphs of $\text{CR}(S)$ induced by classes $A_i$ in $S/_E$ are complete for all $i = 1, 2, \ldots, k$. Let $j\in\{1, 2, \ldots, k\}$ and $a, b\in A_j$. Since $A_j$ is an equivalence class of $S$, $a$ and $b$ are mutually related. Thus $(a, b)\in E$ which implies that an induced subdigraph $[A_j]$ is a complete subdigraph of $\text{CR}(S)$. Furthermore, we obtain $S/_E$ is a pairwise disjoint set since it is a partition of $S$. Hence there is no edge joined between two different vertices where they are in different classes. We conclude that ${\mathop\bigcup\limits^{k}_{i = 1}}[A_i]$ is the disjoint union of complete subdigraphs where each of them is induced by a class in $S/_E$.

Secondly, we will prove that $\text{CR}(S) = {\mathop\bigcup\limits^{k}_{i = 1}}[A_i]$. It suffices to verify that ${\mathop\bigcup\limits^{k}_{i = 1}}[A_i]$ contains $\text{CR}(S)$. Obviously, each vertex of $\text{CR}(S)$ is contained in the vertex set of ${\mathop\bigcup\limits^{k}_{i = 1}}[A_i]$. Consider an arc $(u, v)\in E$. Since $\text{CR}(S)$ is an equivalence digraph, both of $u$ and $v$ must be contained in the same class, say $A_l$ for some $l\in\{1, 2, \ldots, k\}$. More precisely, it is clear that $(u, v)$ is an arc of $[A_l]$. Consequently, $\text{CR}(S) = {\mathop\bigcup\limits^{k}_{i = 1}}[A_i]$, as required.

$(2)\Rightarrow (3) :$ Assume that $\text{CR}(S)$ is the disjoint union of complete subdigraphs $D_1, D_2, \ldots, D_k$. It follows that $\mathcal{P} = \{V(D_1), V(D_2), \ldots, V(D_k)\}$ is a partition of $S$ and $[V(D_j)] = D_j$ is a maximal weakly connected subdigraph of $\text{CR}(S)$. Since $D_j$ is a complete subdigraph of $\text{CR}(S)$, $V(D_j)$ is perfect regular for all $j\in \{1, 2, \ldots, k\}$. Therefore the well-turned property of $\mathcal{P}$ is completely proved.

$(3)\Rightarrow (1) :$ Suppose that $S$ can be partitioned as its disjoint perfect regular subsets $A_1, A_2, \ldots, A_k$ for some $k\in\mathbb{N}$, and suppose that $\mathcal{A} = \{A_1, A_2, \ldots, A_k\}$ is well-turned. We will prove that $E(\text{CR}(S))$ is an equivalence relation on $S$.

Reflexivity : Let $a\in S$. Then $a\in A_i$ for some index $i$. Since $A_i$ is a perfect regular subset of $S$, we have $a = aaa$. Hence $(a, a)\in E(\text{CR}(S))$.

Symmetry : Let $a, b\in S$ and $(a, b)\in E(\text{CR}(S))$. Consider the case where $a\in A_i$ and $b\in A_j$ for some indices $i\neq j$. Thus $a$ and $b$ are vertices of induced subdigraphs $[A_i]$ and $[A_j]$ of $\text{CR}(S)$, respectively. Let $H$ be a subdigraph of $\text{CR}(S)$ whose vertex set is $\{a, b\}$ and arc set is $\{(a, b)\}$. We obtain that $[A_i]\cup[A_j]\cup H$ is a weakly connected subdigraph of $\text{CR}(S)$ containing $[A_i]$ and $[A_j]$. This contradicts to the maximality of $[A_i]$ and $[A_j]$ followed from the well-turned property of the partition $\mathcal{A}$. Therefore, both of vertices $a$ and $b$ must be contained in the same set, say $A_l$ for some index $l$. By the perfect regularity of $A_l$, we get that $b = bab$ which leads to $(b, a)\in E(\text{CR}(S))$.

Transitivity : Let $a, b, c\in S$ be such that $(a, b), (b, c)\in E(\text{CR}(S))$. By the same arguments mentioned above, we can obtain by the well-turned property of $\mathcal{A}$ that $a, b, c\in A_j$ for some index $j$. Again from $A_j$ is a perfect regular subset of $S$, we have $a = aca$. That means $(a, c)\in E(\text{CR}(S))$, as required.

□

Consider $\text{CR}(S_3)$ in Example 1.1. We see that $\text{CR}(S_3)$ is an equivalence digraph which is the disjoint union of two complete subdigraphs $[\{g, i\}]$ and $[\{h, j\}]$. We also see that $\{g, i\}$ and $\{h, j\}$ are perfect regular, and $\{\{g, i\}, \{h, j\} \}$ is well-turned.

4.   Theoretical applications of ${\text{CR}}(S)$

To illustrate some usefulness of Cayley regularity graphs, certain imaginable applications of such digraphs are partly provided in this section. We first apply concepts of the connectedness and completeness to Cayley regularity graph of a semigroup $\mathbb{Z}_n$, the semigroup of integers modulo $n$ under the multiplication. Those structural properties of $\text{CR}(\mathbb{Z}_n)$ are investigated as follows.

Theorem 4.1. Let $n\in \mathbb{N}$ and $\mathit{{CR}}(\mathbb{Z}_n)$ be the Cayley regularity graph of $\mathbb{Z}_n$.

(1) $\mathit{{CR}}(\mathbb{Z}_n)$ is never strongly connected for all $n\geq 2$.

(2) $\mathit{{CR}}(\mathbb{Z}_n)$ is always weakly connected for all $n\geq 2$.

(3) $\mathit{{CR}}(\mathbb{Z}_n)$ is never unilaterally connected for all $n\geq 3$.

(4) $\mathit{{CR}}(\mathbb{Z}_n)$ is never locally connected for all $n\geq 2$.

(5) $\mathit{{CR}}(\mathbb{Z}_n)$ is never complete for all $n\geq 2$.

(6) $\mathit{{CR}}(\mathbb{Z}_n)$ is never semi-complete for all $n\geq 2$.

(7) $\mathit{{CR}}(\mathbb{Z}_n)$ is never directed complete for all $n\geq 3$.

Proof. Let $n\geq 2$. For convenience, we let $\mathbb{Z}_n = \{0, 1, 2, \ldots, n-1\}$.

$(1)$ Since $(x, 0)\notin E(\text{CR}(\mathbb{Z}_n))$ for all $x\in\mathbb{Z}_n\setminus\{0\}$, there is no dipath joining from such elements $x$ to $0$. This implies that $\text{CR}(\mathbb{Z}_n)$ is not strongly connected.

$(2)$ By the structure of $\text{CR}(\mathbb{Z}_n)$, $(0, x)\in E(\text{CR}(\mathbb{Z}_n))$ for all $x\in\mathbb{Z}_n$. Surely, we can find a semidipath between vertices $u$ and $v$ through $0$ for any $u, v\in \mathbb{Z}_n$. Therefore $\text{CR}(\mathbb{Z}_n)$ is weakly connected.

$(3)$ Consider $\text{CR}(\mathbb{Z}_2)$ shown in Figure 2.

We clearly conclude from the definition of unilaterally connectedness that $\text{CR}(\mathbb{Z}_2)$ is unilaterally connected. Next, we consider the case $n\geq 3$. By the definition of having arcs in Cayley regularity graphs, we can say that there exists an arc $(x, y)$ if and only if $y$ is the regular part of $x$ where $x, y$ are vertices of digraphs. Evidently, it is simple to observe that the regular part of $1\in\mathbb{Z}_n$ is only 1 itself. That means $(1, u)\notin E(\text{CR}(\mathbb{Z}_n))$ for all $u\in\mathbb{Z}_n\setminus\{1\}$. We next consider the regular part of $n-1\in\mathbb{Z}_n$. Suppose that $r$ is the regular part of $n-1$. Then $n-1 = (n-1)(r)(n-1) = (n-1)^{2}(r)$. From $(n-1)^{2} = 1\in\mathbb{Z}_n$, the regular part of $n-1$ must be $n-1$, only. This also means that $(n-1, v)\notin E(\text{CR}(\mathbb{Z}_n))$ for all $v\in\mathbb{Z}_n\setminus\{n-1\}$. Consequently, there is no any dipath joining between $1$ and $n-1$ in $\text{CR}(\mathbb{Z}_n)$. Hence $\text{CR}(\mathbb{Z}_n)$ is not unilaterally connected.

$(4)$ As we have described in $(3)$ that there is no dipath going out from $1$ to other vertices, this implies that $\text{CR}(\mathbb{Z}_n)$ is not locally connected because $\text{CR}(\mathbb{Z}_n)$ contains a $[0, 1]$-dipath but not a $[1, 0]$-dipath.

$(5)$ It is not difficult to verify that $\text{CR}(\mathbb{Z}_n)$ is never complete since $(x, 0)\notin E(\text{CR}(\mathbb{Z}_n))$ for all $x\in \mathbb{Z}_n\setminus\{0\}$.

$(6)$ By the construction of $\text{CR}(\mathbb{Z}_n)$, $(1, n-1), (n-1, 1)\notin E(\text{CR}(\mathbb{Z}_n))$ which implies that $\text{CR}(\mathbb{Z}_n)$ is not semi-complete.

$(7)$ Since $(1, 2), (2, 1)\notin E(\text{CR}(\mathbb{Z}_n))$, $\text{CR}(\mathbb{Z}_n)$ is not directed complete.

□

Consider $\text{CR}(\mathbb{Z}_4)$ in Figure 2. We see that $\text{CR}(\mathbb{Z}_4)$ is weakly connected, but not strongly connected, unilaterally connected, locally connected, complete, semi-complete and directed complete.

For further results, Cayley regularity graphs can be used to determine some invariant parameters of graphs or digraphs. In this context, we begin with some descriptions of a commuting graph of a finite group and then consider the edge independence number of the commuting graph. For more basic concepts of commuting graphs, we recommend the readers to ^[13,14,15].

Let $G$ be a finite group and $X$ a nonempty subset of $G$. A commuting graph of a group $G$ associated with the subset $X$, denoted by $\Delta(G, X)$, is defined to be a graph whose vertex set is $X$ and two different vertices are joined by edge if they commute in $G$. If $G$ and $X$ coincide, then $\Delta(G, X)$ will be called a commuting graph of $G$ and shortly denoted by $\Delta(G)$. Moreover, if $G$ is an abelian group, then all commuting graphs induced from $G$ and subsets of $G$ will be complete. Hence, in this case, we consider a non-abelian group $G$ in the construction of its commuting graphs.

For a part of invariant properties of graphs we focus in this context, it is the edge independence number or sometimes called a matching number of a graph. Let $H$ be a finite graph and $E(H)$ a set of all edges of $H$. A nonempty subset $I$ of $E(H)$ is called an edge independent set (matching) of $H$ if all edges in $I$ are pairwise independent, that is, they have no vertex in common. The maximum cardinality among edge independent sets of $H$ is said to be the edge independence number (matching number) of $H$ and will be denoted by $\alpha(H)$. It is easy to check that $\alpha(K_{2n}) = n$. Now, we apply the concept of the Cayley regularity graph to investigate the edge independent number of commuting graphs associated with some special sets.

Let $G$ be a group. Obviously, we see that two vertices of $\text{CR}(G)$ are joined by edge in $\text{CR}(G)$ if and only if they are mutually inverse elements in $G$. That means, for any $a, b\in G$, we have $a = aba$ if and only if $b = a^{-1}$. Actually, if $a$ and $b$ are mutually inverse elements in $G$, then directed edges $(a, b)$ and $(b, a)$ will occur in $\text{CR}(G)$. For convenience, in this part, we will write an undirected edge joining them, denoted by $\{a, b\}$, instead of writing such two directed edges.

Example 4.2. Consider the dihedral group $D_6 = \langle a, x\mid a^6 = x^2 = e, ax = xa^{-1}\rangle$ whose Cayley regularity graph $\text{CR}(D_6)$ is shown in Figure 3. Let $X = \{e, a, a^2, a^3, a^4, a^5\}$. We check at once that each couple of elements in $X$ commute. It follows that $\Delta(D_6, X)\cong K_6$. We thus get $E(\Delta(D_6, X)\cap\text{CR}(D_6)) = \{\{a, a^5\}, \{a^2, a^4\}\}$ is an edge independent set of $\Delta(D_6, X)$.

Lemma 4.1. Let $G$ be a finite group and $X$ a nonempty subset of $G$. Then the commuting graph $\Delta(G, X)\cap\mathit{{CR}}(G)$ is an induced subgraph of $\mathit{{CR}}(G)$ where the edge set $E(\Delta(G, X)\cap\mathit{{CR}}(G))$ forms an edge independent set of $\Delta(G, X)$.

Proof. It is easily seen that $\Delta(G, X)\cap\text{CR}(G)$ is a subgraph of $\text{CR}(G)$. We now let $\{a, b\}\in E(\text{CR}(G))$ where $a, b\in X$. By the definition of $\text{CR}(G)$, we have $a = aba$ and then $b = a^{-1}$ by the above description. Thus $ab = ba$ and it follows that $\{a, b\}\in E(\Delta(G, X))$. This ensures that $\Delta(G, X)\cap\text{CR}(G)$ is an induced subgraph of $\text{CR}(G)$. To investigate the independence of $E(\Delta(G, X)\cap\text{CR}(G))$, let $\{a, b\}, \{c, d\}\in E(\Delta(G, X)\cap\text{CR}(G))$ be such that $\{a, b\}\cap\{c, d\} = \emptyset$. Since two edges lie in $\text{CR}(G)$, we have $b = a^{-1}$ and $d = c^{-1}$. By the uniqueness of an inverse element in a group, we can conclude that such two edges never be adjacent. Therefore $E(\Delta(G, X)\cap\text{CR}(G))$ forms an independent set of $\Delta(G, X)$.

We now present upper and lower bounds of the edge independence number of $\Delta(G, X)$.

□

Theorem 4.3. Let $G$ be a finite group and $X$ a nonempty subset of $G$. Then

where $I$ is a subset of $X$ containing all non-self-inverse elements in $X$.

Proof. By Lemma 4.1, $E(\Delta(G, X)\cap\text{CR}(G))$ forms an independent set of $\Delta(G, X)$. Consequently, $\alpha(\Delta(G, X))\geq |E(\Delta(G, X)\cap\text{CR}(G))|$.

Now, let $I$ be the set containing all non-self-inverse elements in $X$. Without loss of generality, we assume that $I$ is nonempty. Then the graph $\Delta(G, I)\cap\text{CR}(G)$ can be considered as the disjoint union of paths of order $2$ where such two vertices are mutually inverse elements in $G$. Hence $E(\Delta(G, X)\cap\text{CR}(G))$ forms an edge independent set of $\Delta(G, X)$. We now consider an induced subgraph $T$ of $\Delta(G, X)$ induced by $X\setminus I$. It is not complicated to investigate that

since each edge of any graph incident with $2$ vertices. Further, since $\Delta(G, I)\cap\text{CR}(G)$ and $T$ are disjoint and the union of their vertex sets is $X$, we can conclude that

The lower and upper bounds for $\alpha(\Delta(G, X))$ are completely proved.

□

Consider $\Delta(D_6, X)$ in Example 4.2. We have $\alpha(\Delta(D_6, X)) = 3$, because $\Delta(D_6, X)\cong K_6$. Furthermore, we get $\left\lfloor\frac{|X\setminus I|}{2}\right\rfloor = 1$, because $D_6$ has only four non-self-inverse elements $a, a^2, a^4$ and $a^5$. We see that $2\leq\alpha(\Delta(D_6, X))\leq 2+1$.

Surprisingly, if we let $X$ to be the set of all non-self-inverse elements of a finite group $G$, then $E(\Delta(G, X)\cap\text{CR}(G))$ forms a perfect matching of $\Delta(G, X)$ which is a matching such that each vertex of $\Delta(G, X)$ is incident to an edge in $E(\Delta(G, X)\cap\text{CR}(G))$. Moreover, we see that $|X|$ is even and equal to $2|E(\Delta(G, X)\cap\text{CR}(G))|$. Therefore, the following corollary is directly obtained by applying the bounds mentioned in Theorem 4.3.

Corollary 4.1. Let $G$ be a finite group and $X$ the set of all non-self-inverse elements of $G$. Then $\alpha(\Delta(G, X)) = |E(\Delta(G, X)\cap\mathit{{CR}}(G))| = \frac{|X|}{2}$.

Consider the dihedral group $D_6$ in Example 4.2. Let $X = \{a, a^2, a^4, a^5\}$. We get $E(\Delta(D_6, X)\cap\text{CR}(D_6)) = \{\{a, a^5\}, \{a^2, a^4\}\}$ and $\Delta(D_6, X)\cong K_4$, because each couple of elements in $X$ commute. We see that $\alpha(\Delta(D_6, X)) = |E(\Delta(D_6, X)\cap\text{CR}(D_6))| = \frac{|X|}{2} = 2$.

5.   Conclusions

In this research, we introduced the Cayley regularity graph which is a new relation between algebra and graph theory. We presented conditions of semigroups that Cayley regularity graphs satisfy the property of being strongly connected, weakly connected, locally connected, unilaterally connected, complete, semi-complete, directed complete, and equivalence digraphs. Moreover, we applied structural properties of the Cayley regularity graphs to study perfect matchings of commuting graphs of groups.

Acknowledgments

The authors would like to thank the referee(s) for comments and suggestions on the manuscript. This research was supported by Faculty of Science, Khon Kaen University. The corresponding author was supported by Chiang Mai University.