Fractional domination and fractional total domination on Cayley digraphs of transformation semigroups with fixed sets

1.   Introduction

Throughout the paper, all sets are assumed to be finite and nonempty. Let $X$ be a set and $Y$ a subset of $X$. It is well known that $T(X)$ is a semigroup containing all functions from $X$ into itself under the composition of maps. In fact, $T(X)$ is called the full transformation semigroup on the set $X$. Define a semigroup $Fix(X, Y)$ as follows:

Indeed, $Fix(X, Y)$ is a subsemigroup of $T(X)$ and called a transformation semigroup with fixed set which was first introduced by Honyam and Sanwong ^[11] in 2013. In this content, we write functions on the right. Particularly, for the composition $\alpha\beta$ of $\alpha, \beta\in T(X)$, we mean that $\alpha$ is applied first. An algebraic object, relative to graph theory and semigroup theory, our focus in this paper is the Cayley digraph, which is defined as follows. Let $A$ be a subset of $Fix(X, Y)$. The Cayley digraph $\text{Cay}(Fix(X, Y), A)$ of $Fix(X, Y)$ with respect to $A$ is defined as a digraph (without multiple arcs) with vertex set $Fix(X, Y)$ and arc set consisting of ordered pairs $(\alpha, \beta)$ where $\beta = \alpha\lambda$ for some $\lambda\in A$. The set $A$ is called a connection set of the Cayley digraph $\text{Cay}(Fix(X, Y), A)$. For convenience, we write $\Gamma$ instead of $\text{Cay}(Fix(X, Y), A)$. Recently, there are some researches related to Cayley digraphs of $Fix(X, Y)$. For example, in 2020, Nupo and Pookpienlert ^[15] presented some prominent results on $\Gamma$ relative to minimal idempotents. In 2021, they investigated in ^[14] the domination parameters of $\Gamma$ where the connection sets contain only minimal idempotents or permutations. The major objects focused on in the present paper are related to Cayley digraphs of $Fix(X, Y)$ with respect to minimal idempotents and permutations.

Graph theory is one of the branches of modern mathematics having experienced the most impressive development in recent years. Several applications can be found in game theory, management sciences, and transportation network theory. The next step of the evolution is related to fractional graph theory. By developing the fractional idea, the purpose of researchers is multiple. First, to enlarge the scope of applications in scheduling, operations research, and various kinds of assignment problems. Second, to simplify those such problems. The fractional version of a theorem is frequently easier to prove than the classical one. Further, a bound for a fractional coefficient of a graph is also a bound for the classical coefficient or suggests a conjecture. In 1987, Hedetniemi et al. ^[10] introduced the fractional domination concept in graphs. The fractional parameters we consider in this paper are fractional domination and fractional total domination numbers. Many researchers are interested in the concepts of fractional parameters in graphs and digraphs. In 1990, Fricke et al. ^[7] determined the computational complexity of the fractional total domination number of graphs and described a linear time algorithm to find such parameter for trees. In 1994, Fisher ^[4] showed the relations of the 2-packing number, fractional domination number, and domination number of the Cartesian product graphs. Moreover, Fisher et al. ^[6] proved the fractional domination of strong direct products of graphs. In addition, Hare ^[8] studied the fractional domination number of the $m\times n$ complete grid graph, which is isomorphic to the product of two paths $P_m\times P_n$. In 2002, Fisher ^[5] considered the fractional domination number and the fractional total domination number of graphs and their complements. In 2007, Walsh ^[21] presented the fractional domination number of prisms. In the same year, Arumugam and Rejikumar ^[2] proposed several results for the fractional domination chain in graphs. In 2009, Rubalcaba and Walsh ^[17] investigated some structural properties of the fractional dominating functions of graphs. In 2012, Arumugam et al. ^[1] studied the fractional version of distance k-domination and related parameters. In 2015, Sangeetha and Maheswari ^[18] introduced the minimal dominating functions of Euler Totient Cayley graphs. In 2018, Harutyunyan et al. ^[9] presented an upper bound of the fractional domination number of digraphs in terms of independence number of their underlying graphs. In 2021, Karunambigai and Sathishkumar ^[13] introduced the dominating functions on fractional graphs and found the fractional domination number of certain graphs by formulating the linear programming problem. In 2023, Shanthi et al. ^[20] analyzed the effects on the fractional domination number of a graph $G$ after deleting a vertex from $G$. Additionally, some bounds of the parameter are discussed and proved using the eccentricity value of a vertex of $G$.

In this contribution, we are interested to investigate the fractional concepts of domination parameters on Cayley digraphs $\Gamma$ of transformation semigroups with fixed sets. We divide the paper into six sections. The introduction and preliminaries are provided in Sections 1 and 2, respectively. In Section 3, we present the fractional (total) domination numbers on $\Gamma$ with respect to minimal idempotents. We prove that if all elements in the connection set of $\Gamma$ are minimal idempotents, then the fractional domination number of $\Gamma$ is equal to the domination number. However, the fractional total domination number of $\Gamma$ does not exist. Moreover, we determine the fractional domination number and fractional total domination number of $\Gamma$ with respect to permutations in Sections 4 and 5, respectively. Finally, we summarize the work in the conclusion provided in Section 6.

2.   Preliminaries and notations

Let $D$ be a digraph with vertex set $V$ and arc set $E$. Assume that $D$ admits loops and excludes multiple edges. A dominating set of $D$ is a set $S$ of vertices such that every vertex in $V\backslash S$ has an in-neighbor in $S$. The domination number $\gamma(D)$ of $D$ is defined to be the cardinality of the smallest dominating set. Further, a total dominating set of $D$ is a set $S$ of vertices such that every vertex in $V$ has an in-neighbor in $S$. Similarly, the total domination number $\gamma_t(D)$ is the cardinality of the smallest total dominating set of $D$. Let $S$ be a dominating set of $D$ and $f:V\to\{0, 1\}$ be the characteristic function on $S$, so that

The dominating property of $S$ is equivalent to

for every $v\in V$, where $N^-[v] = N^-(v)\cup\{v\}$ in which $N^-(v)$ is the set of in-neighbors of $v$ in $D$. That is, $N^-(v) = \{u\in V\backslash\{v\} : (u, v)\in E\}$. Similarly, for each $v\in V$, one can define $N^+[v] = N^+(v)\cup\{v\}$ where $N^+(v) = \{u\in V\backslash\{v\} : (v, u)\in E\}$ is the set of all out-neighbors of $v$ in $D$. Moreover, the in-degree $d^-(v)$ and out-degree $d^+(v)$ of $v$ in $D$ are defined to be $|N^-(v)|$ and $|N^+(v)|$, respectively. Furthermore, if $(v, v)\in E$ and $N^-(v) = \emptyset = N^+(v)$, then we say that $v$ is an isolated loop in $D$. Fractional graph theory deals with the generalization of integer-valued graph theoretic concepts such that they take on fractional values. One of the standard methods for converting a graph concept from integer to fractional is to formulate the concept as an integer program and then to consider the linear programming relaxation. A detailed study of fractional graph theory and fractionalization of various graph parameters are given by Scheinerman and Ullman ^[19] in 1997.

Let $D = (V, E)$ be a digraph and $f:V\to\mathbb{R}$ be a real-valued function. For any subset $S$ of $V$, we let $f(S) = \mathop{\sum}\limits_{x\in S}{f(x)}$. The weight of $f$ is defined by $|f| = f(V)$. The fractional analogues of invariants for a digraph $D = (V, E)$ may be obtained as the linear relaxation of the associated integer programs or combinatorically as follows.

A function $f:V\to[0, 1]$ is called a fractional dominating function of $D$ if

for every $v\in V$. The fractional domination number of $D$, denoted by $\gamma^*(D)$, is the minimum weight of a fractional dominating function of $D$, that is,

Similarly, one can define a fractional total dominating function of $D$ and the fractional total domination number $\gamma_t^*(D)$ of $D$ by replacing $N^-[v]$ with $N^-(v)$. That is,

Hereafter, some preliminaries and relevant information about digraphs can be found in ^[16] and others on semigroups can be seen in ^[3] and ^[12]. We now present some concepts and notations related to the semigroup $Fix(X, Y)$. For convenience, we write $Y = \{a_i : i\in I\}$. For each $\alpha\in Fix(X, Y)$, we then have $a_i\alpha = a_i$ for all $i\in I$. Further, the image of $\alpha$ is denoted by $X\alpha = Y \dot{\cup} \{b_j : j\in J\}$. Note that the index set $J$ could be empty, that is, $X\alpha = Y$. Consequently, $\alpha$ can be written as follows:

where $A_i = a_i\alpha^{-1}$ for each $i\in I$ and $B_j = b_j\alpha^{-1}$ for each $j\in J$. We can observe that $A_i\cap Y = \{a_i\}$ for each $i\in I$ and $B_j\subseteq X\backslash Y$ for each $j\in J$. Moreover, Honyam and Sanwong ^[11] proved that the set $E_m$ of all minimal idempotents in $Fix(X, Y)$ are as follows:

Further, denote by $H_{id_X}$ the group of all permutations in $Fix(X, Y)$ where $id_X$ is the identity map of $Fix(X, Y)$. It is clear that $Fix(X, Y) = \{id_X\}$ whenever $X = Y$, so we consider the case $Y\subsetneq X$ throughout the paper. Obviously, if $id_X$ is an element of a connection set of the Cayley digraph $\Gamma$, then $\Gamma$ contains loops attached to each vertex. Therefore, we consider only the case that all connection sets exclude the identity map $id_X$.

3.   Fractional (total) domination on $\Gamma$ with respect to minimal idempotents

In this section, we provide results for the fractional domination number and the fractional total domination number of $\Gamma$ whose connection sets are contained in $E_m$.

Theorem 3.1. If $A\subseteq E_m$ is a connection set of $\Gamma$, then $\gamma^*(\Gamma) = \gamma(\Gamma)$.

Proof. Let $A\subseteq E_m$ be a connection set of $\Gamma$. Define the sets $\mathcal{A}$ and $\mathcal{B}$ as follows.

By [14, Lemma 3.3], we conclude that $\mathcal{B}$ is a dominating set of $\Gamma$. Define the characteristic function $f:Fix(X, Y)\to[0, 1]$ on $\mathcal{B}$ by

It is not hard to verify that $f$ is a fractional dominating function of $\Gamma$. Let $\beta\in\mathcal{B}$. We now prove that $N^-(\beta) = \emptyset$. Suppose to the contrary that there exists $\eta\in Fix(X, Y)$ such that $\eta\in N^-(\beta)$, that is, $(\eta, \beta)\in E(\Gamma)$. Thus $\beta = \eta\mu$ for some $\mu\in A\subseteq E_m$. For each $x\in X$, we see that $x\beta = x(\eta\mu) = (x\eta)\mu\in Y$ which yields that $\beta\in E_m$. If $\eta\in E_m$, then $\beta = \eta\mu = \eta\in N^-(\beta)$ which is impossible. So we conclude that $\eta\notin E_m$. Then there exists $z\in X\backslash Y$ in which $z\eta\in X\backslash Y$. By the fact that $\beta, \mu\in E_m$ and $z\beta = z(\eta\mu) = (z\eta)\mu \in (X\backslash Y)\mu$, we have

We obtain that $\beta\in\mathcal{A}$ which is a contradiction. Hence $N^-(\beta) = \emptyset$ for all $\beta\in\mathcal{B}$. Furthermore, it is proved in [14, Theorem 3.4] that $\mathcal{B}$ is the minimum dominating set of $\Gamma$. This implies that $|f|$ must be the minimum size among fractional dominating functions of $\Gamma$. Therefore, $\gamma^*(\Gamma) = |f| = |\mathcal{B}| = \gamma(\Gamma)$. □

Actually, if a connection set of $\Gamma$ is contained in $E_m$, then every non-minimal idempotent has zero in-degree. Thus we can not define any fractional total dominating function of $\Gamma$ and we then get the following proposition.

Proposition 3.2. If $A\subseteq E_m$ is a connection set of $\Gamma$, then $\gamma^*_t(\Gamma)$ does not exist.

4.   Fractional domination on $\Gamma$ with respect to permutations

In semigroup theory, the Green's equivalence relations $\mathcal{L}, \mathcal{R}$ and $\mathcal{H}$ on $Fix(X, Y)$ are defined as follows. For convenience, let $S = Fix(X, Y)$ and for $\alpha, \beta\in S$,

Moreover, for each $\alpha\in S$, we denote the equivalence $\mathcal{H}$-class containing $\alpha$ by $H_\alpha$. That is,

We now present the fractional domination number of $\Gamma$ whose connection sets are contained in $H_{id_X}\backslash\{id_X\}$. Clearly, if $|X\backslash Y| = 1$, then $H_{id_X} = \{id_X\}$ and yields that $A = \emptyset$. So we focus on the case $|X\backslash Y|\geq 2$. By [14, Theorem 4.1], we obtain that $\Gamma$ is the disjoint union of induced subdigraphs $\Gamma[E_m], \Gamma[H_{id_X}]$, and $\Gamma[G]$ where $G = Fix(X, Y)\backslash(E_m\cup H_{id_X})$. Thus we will propose results by considering each induced subdigraph, independently. However, if $A = H_{id_X}\backslash\{id_X\}$, then we obtain the fractional domination number of $\Gamma$ as follows.

Proposition 4.1. If $A = H_{id_X}\backslash\{id_X\}$ is a connection set of $\Gamma$, then $\gamma^*(\Gamma) = \gamma(\Gamma)$.

Proof. Let $A = H_{id_X}\backslash\{id_X\}$ be a connection set of $\Gamma$. By following the proof of [14, Proposition 4.4], we conclude that $\Gamma$ is the disjoint union of $\Gamma[R_\alpha]$ where $\Gamma[R_\alpha]$ is a complete subdigraph of $\Gamma$ induced by an $\mathcal{R}$-class of $Fix(X, Y)$ containing $\alpha\in Fix(X, Y)$. By choosing one vertex from each subdigraph and let $U$ be the set of such vertices, we obtain that $\gamma(\Gamma) = |U|$. Further, by considering the characteristic function on the set $U$, we observe that it is a fractional dominating function of $\Gamma$ and yields that $\gamma^*(\Gamma) = |U| = \gamma(\Gamma)$. □

We next study the fractional domination number of $\Gamma$ where a connection set $A$ is a proper subset of $H_{id_X}\backslash\{id_X\}$ by considering $\Gamma[E_m], \Gamma[H_{id_X}]$, and $\Gamma[G]$, respectively.

Theorem 4.2. If $A\subsetneq H_{id_X}\backslash\{id_X\}$ is a connection set of $\Gamma$, then $\gamma^*(\Gamma[E_m]) = |Y|^{|X|-|Y|}$.

Proof. Let $A\subsetneq H_{id_X}\backslash\{id_X\}$ be a connection set of $\Gamma$. In $\Gamma[E_m]$, we see that every minimal idempotent is an isolated loop and then $N^-(\mu) = \emptyset = N^+(\mu)$ for all $\mu\in E_m$. By defining the constant map $f(\mu) = 1$ for all $\mu\in E_m$, we get that $f$ is a fractional dominating function of $\Gamma$ which is also minimum. Thus $\gamma^*(\Gamma[E_m]) = |f| = |E_m| = |Y|^{|X|-|Y|}$. □

Theorem 4.3. If $A\subsetneq H_{id_X}\backslash\{id_X\}$ is a connection set of $\Gamma$, then $\gamma^*(\Gamma[H_{id_X}]) = \dfrac{|X\backslash Y|!}{|A|+1}$.

Proof. Let $A\subsetneq H_{id_X}\backslash\{id_X\}$ be a connection set of $\Gamma$. For convenience, we may assume that $A = \{\alpha_1, \alpha_2, \ldots, \alpha_k\}$ for some $k\in \mathbb{N}$. By the property of the group $H_{id_X}$, we can conclude that, for each $\alpha\in H_{id_X}$, elements of $\{\alpha\alpha_1, \alpha\alpha_2, \ldots, \alpha\alpha_k\}$ are all distinct. Further, we can observe that $N^+(\alpha) = \{\alpha\alpha_1, \alpha\alpha_2, \ldots, \alpha\alpha_k\}$ which implies that $d^+(\alpha) = |N^+(\alpha)| = |A|$. Similarly, we can summarize that $N^-(\alpha) = \{\alpha\alpha^{-1}_1, \alpha\alpha^{-1}_2, \ldots, \alpha\alpha^{-1}_k\}$ and so $d^-(\alpha) = |N^-(\alpha)| = |A|$. Therefore, $d^-(\alpha) = |A| = d^+(\alpha)$ for all $\alpha\in H_{id_X}$. By [9, Proposition 2.7], we have

On the other hand, let $f:H_{id_X}\to[0, 1]$ be defined by $f(\lambda) = \dfrac{1}{|A|+1}$ for all $\lambda\in H_{id_X}$. We now show that $f$ is a fractional dominating function of $\Gamma[H_{id_X}]$. Let $\lambda\in H_{id_X}$. Consider

this implies that $f$ is a fractional dominating function of $\Gamma[H_{id_X}]$, immediately. It follows that

Consequently, we have $\gamma^*(\Gamma[H_{id_X}]) = \dfrac{|X\backslash Y|!}{|A|+1}$, as desired. □

Generally, the structure of $\Gamma[G]$ is more complicated than the other two subdigraphs $\Gamma[E_m]$ and $\Gamma[H_{id_X}]$. This yields that the fractional domination number of $\Gamma[G]$ is quite difficult to be determined. Hence we attempt to investigate the lower and upper bounds of $\gamma^*(\Gamma[G])$. However, the following lemma is needed.

Lemma 4.4. If $A\subseteq H_{id_X}\backslash\{id_X\}$ is a connection set of $\Gamma$, then $\Delta^+(\Gamma[G]) = |A|$ where $\Delta^+(\Gamma[G])$ is the maximum out-degree of $\Gamma[G]$ without considering loops.

Proof. Let $A\subseteq H_{id_X}\backslash\{id_X\}$ be a connection set of $\Gamma$. Further, let $y\in Y$ and $z\in X\backslash Y$. Define $\lambda\in G$ by

We now prove that elements in the set $\lambda A = \{\lambda\alpha : \alpha\in A\}$ are all distinct. Assume that $\lambda\alpha = \lambda\beta$ for some $\alpha, \beta\in A$. Let $x\in X\backslash\{z\}$. Then $x\alpha = (x\lambda)\alpha = x(\lambda\alpha) = x(\lambda\beta) = (x\lambda)\beta = x\beta$. Since $\alpha, \beta\in A\subseteq H_{id_X}\backslash\{id_X\}$, we obtain that $z\alpha = z\beta$. Hence $\alpha = \beta$. Thus elements in the set $\lambda A$ are all distinct. We next show that $\lambda\notin\lambda A$. If $\lambda = \lambda\alpha$ for some $\alpha\in A$, then $x\alpha = (x\lambda)\alpha = x(\lambda\alpha) = x\lambda = x$ for all $x\in X\backslash\{z\}$. From $\alpha\in H_{id_X}\backslash\{id_X\}$, we have $z\alpha = z$. This yields that $\alpha = id_X$ which is a contradiction. Consequently, $N^+(\lambda) = \lambda A$ which implies that $d^+(\lambda) = |A|$. As the fact that $N^+(\mu)\subseteq \mu A$ for all $\mu\in \Gamma$, we have $\Delta^+(\Gamma[G]) = d^+(\lambda) = |A|$. □

Theorem 4.5. If $A\subsetneq H_{id_X}\backslash\{id_X\}$ is a connection set of $\Gamma$, then

where $\delta^-: = \delta^-(\Gamma[G])$ is the minimum in-degree of $\Gamma[G]$ without considering loops.

Proof. Assume that $A\subsetneq H_{id_X}\backslash\{id_X\}$ is a connection set of $\Gamma$. By [9, Proposition 2.7], we obtain that $\gamma^*(\Gamma[G])\geq\dfrac{|G|}{\Delta^++1}$ where $\Delta^+: = \Delta^+(\Gamma[G])$ is the maximum out-degree of $\Gamma[G]$. Moreover, we get by Lemma 4.4 that $\Delta^+(\Gamma[G]) = |A|$. Thus the lower bound, $\gamma^*(\Gamma[G])\geq\dfrac{|G|}{|A|+1}$, is proved. In order to verify the upper bound, we define a function $f:G\to[0, 1]$ by $f(\alpha) = \dfrac{1}{\delta^-+1}$ for all $\alpha\in G$. Obviously, $\delta^-\leq|N^-(\alpha)|$ for all $\alpha\in G$. So it is not hard to consider that, for each $\alpha\in G$,

Thus, $f$ is a fractional dominating function of $\Gamma[G]$ which yields that $\gamma^*(\Gamma[G])\leq|f| = \mathop{\sum}\limits_{\alpha\in G}{f(\alpha)} = \dfrac{|G|}{\delta^-+1}$. Clearly, $\gamma^*(\Gamma[G])\leq\gamma(\Gamma[G])$. Therefore,

□

We now describe some terminologies related to the expression of permutations. Let $\alpha\in H_{id_X}$. In fact, every permutation can be written as the product of disjoint cycles. Therefore, we can write $\alpha$ as follows:

such that, for each $k = 1, 2, \ldots, r$, there exist $c_1, c_2, \ldots, c_s\in X$ in which $c_1\delta_k = c_2, c_2\delta_k = c_3, \ldots, c_{s-1}\delta_k = c_s$, and $c_s\delta_k = c_1$. For convenience, $\delta_k$ is called a subcycle of length $s$ in the permutation $\alpha$. Furthermore, if there exists $l\in \{1, 2, \ldots, r\}$ such that $\delta_l$ is a subcycle of odd length in $\alpha$, then we say that $\alpha$ contains an odd subcycle. Otherwise, it does not contain an odd subcycle.

To investigate the equality of bounds stated in Theorem 4.5, we consider a singular connection set and obtain the parameter $\gamma^*(\Gamma[G])$ as follows.

Proposition 4.6. Let $A = \{\alpha\}\subseteq H_{id_X}\backslash\{id_X\}$ be a connection set of $\Gamma$. If no element in $X\backslash Y$ is a fixed point of $\alpha$, then

where $t$ is the number of odd directed cycles in $\Gamma[G]$.

Proof. Assume that no element in $X\backslash Y$ is a fixed point of $\alpha$. We first show that $\Gamma[G]$ is the disjoint union of directed cycles. To show this, it suffices to prove that $d^-(\lambda) = 1 = d^+(\lambda)$ for all $\lambda\in G$. Let $\lambda\in G$. Clearly, $d^+(\lambda) = 1$. Further, we easily observe that $\lambda_1\beta = \lambda_2\beta$ if and only if $\lambda_1 = \lambda_2$ whenever $\lambda_1, \lambda_2\in G$ and $\beta\in H_{id_X}$. Thus $d^-(\lambda) = 1$. Hence $\Gamma[G]$ is the disjoint union of directed cycles.

$\textbf{Case 1.}$ $\alpha$ does not contain an odd subcycle of length greater than $1$. We need to show that those directed cycles in $\Gamma[G]$ are of even length. Suppose that there exists a directed cycle $\overrightarrow{C_k}$ of odd length $k$ in $\Gamma[G]$. For convenience, let $\overrightarrow{C_k} : = \lambda_1, \lambda_2, \ldots, \lambda_k, \lambda_1$. We obtain that $\lambda_k = \lambda_{k-1}\alpha = \lambda_{k-2}\alpha^2 = \ldots = \lambda_2\alpha^{k-2} = \lambda_1\alpha^{k-1}$ and $\lambda_1 = \lambda_k\alpha$. Then $\lambda_k = \lambda_1\alpha^{k-1} = (\lambda_k\alpha)\alpha^{k-1} = \lambda_k\alpha^k$. Since $\lambda_k\in G$, there exists $b\in X\backslash Y$ such that $b\lambda_k\in X\backslash Y$. By assumption, we have $(b\lambda_k)\alpha\neq b\lambda_k$. Let $p$ be the smallest positive integer such that $(b\lambda_k)\alpha^p = b\lambda_k$. As the fact that $\alpha$ does not contain an odd subcycle of length greater than $1$, we obtain that $p$ is even. If $p < k$, then by Division's algorithm, $k = qp+r$ for some $q\in\mathbb{N}$ and $1\leq r < p$. Thus $b\lambda_k = b\lambda_k\alpha^k = (b\lambda_k)\alpha^k = (b\lambda_k)\alpha^{qp+r} = (b\lambda_k)\alpha^{qp}\alpha^r = (b\lambda_k)\alpha^r$ which is impossible since $r < p$. If $p > k$, then $(b\lambda_k)\alpha^k = b(\lambda_k\alpha^k) = b\lambda_k$. This also leads to a contradiction. Hence every induced directed cycle in $\Gamma[G]$ has even length. We now define the function $f:G\to[0, 1]$ by $f(\beta) = \dfrac{1}{2}$ for all $\beta\in G$. It is not complicated to conclude that $f$ is a minimum fractional dominating function of $\Gamma[G]$. Therefore, $\gamma^*(\Gamma[G]) = |f| = \dfrac{1}{2}|G| = \gamma(\Gamma[G])$.

$\textbf{Case 2.}$ $\alpha$ contains an odd subcycle of length greater than $1$. Let $(a_1\, a_2\, \ldots\, a_k)$ be an odd subcycle of $\alpha$ for some odd positive integer $k\geq 3$. Define $\lambda\in Fix(X, Y)$ by

We obtain that $\lambda, \lambda\alpha, \lambda\alpha^2, \ldots, \lambda\alpha^{k-1}, \lambda\alpha^{k} = \lambda$ form a directed cycle of length $k$. In this case, we observe that $\lambda, \lambda\alpha, \lambda\alpha^2, \ldots, \lambda\alpha^{k-1}\in G$. That is, $\Gamma[G]$ contains an induced directed cycle of odd length. Let $t$ be the number of odd directed cycles in $\Gamma[G]$. It is easily investigated that if $r$ is an odd number, then $\gamma(\overrightarrow{C_r}) = \dfrac{r+1}{2}$. Let $g:V(\overrightarrow{C_r})\to[0, 1]$ be defined by $g(\beta) = \dfrac{1}{2}$ for all $\beta\in V(\overrightarrow{C_r})$. Then $\gamma^*(\overrightarrow{C_r}) \leq \dfrac{r}{2}$. By [9, Proposition 2.7], we have $\gamma^*(\overrightarrow{C_r})\geq \dfrac{r}{2}$ and hence $\gamma^*(\overrightarrow{C_r}) = \dfrac{r}{2} = \dfrac{r+1}{2}-\dfrac{1}{2} = \gamma(\overrightarrow{C_r})-\dfrac{1}{2}$. Consequently,

Using the minimum fractional dominating function $f$ of $\Gamma[G]$ defined in Case 1, we also have $\gamma^*(\Gamma[G]) = |f| = \dfrac{1}{2}|G|$. Hence the result is proved. □

5.   Fractional total domination on $\Gamma$ with respect to permutations

Next, we will study the fractional total domination number of $\Gamma$ for a connection set $A$ which is a subset of $H_{id_X}\backslash\{id_X\}$. Recall that a function $f:Fix(X, Y)\to [0, 1]$ is called a fractional total dominating function of $\Gamma$ if

for every $\alpha\in Fix(X, Y)$. The fractional total domination number of $\Gamma$ is the minimum weight of a fractional total dominating function of $\Gamma$ which is denoted by $\gamma^*_t(\Gamma)$. That is,

We observed in the proof of Theorem 4.2 that, for a connection set $A\subseteq H_{id_X}\backslash\{id_X\}$, all minimal idempotents have zero in-degree in $\Gamma$. Consequently, we cannot define any fractional total dominating function of $\Gamma$. Therefore, the fractional total domination number of $\Gamma$ does not exist. Hence, we aim to investigate this parameter for the induced subdigraphs $\Gamma[H_{id_X}], \Gamma[E_m]$ and $\Gamma[G]$.

As we mentioned above, all minimal idempotents have zero in-degree in $\Gamma$ which implies that $\gamma^*_t(\Gamma[E_m])$ does not exist. For results on the fractional total domination numbers of $\Gamma[H_{id_X}]$ and $\Gamma[G]$, we present as follows. By [15, Theorem 4.5], we have known that $\Gamma$ is locally connected. Hence $N^-(\alpha)\neq\emptyset$ for all $\alpha\in H_{id_X}$. Consequently, the fractional total domination number of $\Gamma[H_{id_X}]$ always exists.

Theorem 5.1. If $A\subseteq H_{id_X}\backslash\{id_X\}$ is a connection set of $\Gamma$, then $\gamma^*_t(\Gamma[H_{id_X}]) = \dfrac{|X\backslash Y|!}{|A|}$.

Proof. Assume that $A = \{\alpha_1, \alpha_2, \ldots, \alpha_k\}$. Let $\lambda\in H_{id_X}$. Clearly, $N^-(\lambda) = \{\lambda\alpha^{-1}_1, \lambda\alpha^{-1}_2, \ldots, \lambda\alpha^{-1}_k\}$ where $\lambda\alpha^{-1}_i\neq\lambda\alpha^{-1}_j$ for all $i\neq j\in\{1, 2, \ldots, k\}$. That is, $d^-(\lambda) = |N^-(\lambda)| = |A|$. We now define $f:H_{id_X}\to[0, 1]$ by $f(\beta) = \dfrac{1}{|A|}$ for all $\beta\in H_{id_X}$. Hence

Next, let $g$ be arbitrary fractional total dominating function of $\Gamma[H_{id_X}]$. Then $g(N^-(\delta))\geq 1 = f(N^-(\delta))$ for all $\delta\in H_{id_X}$ which implies that

Therefore, we can conclude that $f$ is the minimum fractional total dominating function of $\Gamma[H_{id_X}]$. Consequently, $\gamma^*_t(\Gamma[H_{id_X}]) = |f| = \dfrac{|H_{id_X}|}{|A|} = \dfrac{|X\backslash Y|!}{|A|}$, as required. □

We now provide the characterization for an existence of the fractional total domination number of $\Gamma[G]$. For each $\alpha\in Fix(X, Y)$, define $Fix(\alpha) = \{x\in X : x\alpha = x\}$.

Theorem 5.2. Let $A\subseteq H_{id_X}\backslash\{id_X\}$ be a connection set of $\Gamma$. Then the following statements are equivalent.

(i) The fractional total domination number of $\Gamma[G]$ exists.

(ii) $N^-(\eta)\neq\emptyset$ for all $\eta\in G$.

(iii) $\mathop{\bigcap}\limits_{\alpha\in A}{Fix(\alpha)} = Y$.

Proof. Obviously, the statements (ⅰ) and (ⅱ) are equivalent. We now prove that (ⅱ) and (ⅲ) are equivalent.

(ⅱ)$\Rightarrow$(ⅲ): Assume that $N^-(\eta)\neq\emptyset$ for all $\eta\in G$. Suppose that there exists $x\in X\backslash Y$ such that $x\in \mathop{\bigcap}\limits_{\alpha\in A}{Fix(\alpha)}$. Consider $\lambda\in G$ defined by

By assumption, there exists $\beta\in N^-(\lambda)$, that means $\beta\neq\lambda$. Then $(\beta, \lambda)\in E(\Gamma)$, that is, $\lambda = \beta\mu$ for some $\mu\in A$. Let $z\in X\backslash Y$. Thus $x = z\lambda = z(\beta\mu) = (z\beta)\mu$. Since $x\in Fix(\mu)$ and $\mu\in A\subseteq H_{id_X}$, we get that $z\beta = x$. Hence $\beta = \lambda$ which is a contradiction.

(ⅲ)$\Rightarrow$(ⅱ): Assume that $\mathop{\bigcap}\limits_{\alpha\in A}{Fix(\alpha)} = Y$. Let $\eta\in G$. Then we can write

Since $\mathop{\bigcap}\limits_{\alpha\in A}{Fix(\alpha)} = Y$, there exists $\lambda\in A$ such that $(X\backslash Y)\eta\nsubseteq Fix(\lambda)$. Hence there exists $b_k\in (X\backslash Y)\eta$ in which $b_k\notin Fix(\lambda)$. That is, $b_k\lambda\neq b_k$ which implies that $b_k\lambda^{-1}\neq b_k$. Define $\mu\in Fix(X, Y)$ by

We can obtain that $\mu\in G\backslash\{\eta\}$ and $\mu\lambda = \eta$. Thus $(\mu, \eta)\in E(\Gamma[G])$ and so $\mu\in N^-(\eta)$. Therefore, $N^-(\eta)\neq\emptyset$. □

To present results on the fractional total domination number of $\Gamma[G]$, we need the following lemma.

Lemma 5.3. Let $\lambda\in G$ and $\alpha\in A$. Then $X\lambda\subseteq Fix(\alpha)$ if and only if $\lambda = \lambda\alpha$.

Proof. Assume that $X\lambda\subseteq Fix(\alpha)$. Let $x\in X$. Then $x\lambda\in X\lambda\subseteq Fix(\alpha)$. Hence $x\lambda = (x\lambda)\alpha = x(\lambda\alpha)$ which implies that $\lambda = \lambda\alpha$.

Conversely, assume that $\lambda = \lambda\alpha$. Let $a\in X\lambda$. Then $a = b\lambda$ for some $b\in X$. Thus $a\alpha = (b\lambda)\alpha = b(\lambda\alpha) = b\lambda = a$. Therefore, $a\in Fix(\alpha)$ which yields that $X\lambda\subseteq Fix(\alpha)$. □

Moreover, we aim to investigate some prominent properties of $\Gamma[G]$ via an equivalence relation defined as follows.

Let $A$ be a connection set of $\Gamma$ in which $\mathop{\bigcap}\limits_{\alpha\in A}{Fix(\alpha)} = Y$. For each $\lambda\in G$, we define $A_\lambda\subseteq A$ by

Hence $A_\lambda\neq\emptyset$. Further, we define a relation $\sim_\lambda$ on $A_\lambda$ by, for each $\alpha, \beta\in A_\lambda$,

Clearly, the relation $\sim_\lambda$ is an equivalence relation on $A_\lambda$. Let $A_\lambda / \sim_\lambda$ be the set of all equivalence classes of $A_\lambda$ with respect to $\sim_\lambda$. In addition, denote by the notation $1_{A_\lambda}$ the equivalence relation $\{(\alpha, \alpha) : \alpha\in A_\lambda\}$. We then obtain the following theorem.

Theorem 5.4. Let $A\subseteq H_{id_X}\backslash\{id_X\}$ be a connection set of $\Gamma$ in which $\mathop{\bigcap}\limits_{\alpha\in A}{Fix(\alpha)} = Y$. If $\lambda\in G$, then $N^-(\lambda)$ is one-to-one corresponding to $A_\lambda / \sim_\lambda$. Consequently, $d^-(\lambda) = \left|A_\lambda / \sim_\lambda\right|$.

Proof. Let $\lambda\in G$. By Theorem 5.2, we have $N^-(\lambda)\neq\emptyset$. Let $\alpha\in N^-(\lambda)$. Then there exists $\beta\in A$ such that $\lambda = \alpha\beta$, that is, $\alpha = \lambda\beta^{-1}$. We first show that $\beta\in A_\lambda$. Suppose that $X\lambda\subseteq Fix(\beta)$. For each $x\in X$, we obtain that $x(\lambda\beta) = (x\lambda)\beta = x\lambda = x(\alpha\beta)$. Thus $\lambda\beta = \alpha\beta$ and so $\lambda = \alpha$ which is impossible since $\alpha\in N^-(\lambda)$. Hence $X\lambda\nsubseteq Fix(\beta)$ which implies that $\beta\in A_\lambda$. Define $\varphi:N^-(\lambda)\to A_\lambda / \sim_\lambda$ by $\varphi(\lambda\beta^{-1}) = \beta\sim_\lambda$. For each $\lambda\beta^{-1}, \lambda\mu^{-1}\in N^-(\lambda)$, assume that $\lambda\beta^{-1} = \lambda\mu^{-1}$. For each $x\in (X\backslash Y)\lambda^{-1}$, we have $x(\lambda\beta^{-1}) = x(\lambda\mu^{-1})$. Then $\beta\sim_\lambda\mu$ which means that $\beta\sim_\lambda = \mu\sim_\lambda$. Hence $\varphi$ is well-defined. We next show that $\varphi$ is a bijection. Let $\lambda\beta^{-1}, \lambda\mu^{-1}\in N^-(\lambda)$ be such that $\varphi(\lambda\beta^{-1}) = \varphi(\lambda\mu^{-1})$. Then $\beta\sim_\lambda = \mu\sim_\lambda$, that is, $\beta\sim_\lambda\mu$. Thus $x\lambda\beta^{-1} = x\lambda\mu^{-1}$ for all $x\in (X\backslash Y)\lambda^{-1}$. Furthermore, for each $x\in Y\lambda^{-1}$, we have $x\lambda\in Y$ and hence $x\lambda\beta^{-1} = x\lambda = x\lambda\mu^{-1}$. Therefore, $\lambda\beta^{-1} = \lambda\mu^{-1}$ which yields that $\varphi$ is injective. For proving that $\varphi$ is surjective, let $\beta\sim_\lambda\in A_\lambda / \sim_\lambda$. Thus $\beta\in A_\lambda$ which implies that $X\lambda\nsubseteq Fix(\beta)$. Let $\mu = \lambda\beta^{-1}$. By Lemma 5.3, we obtain that $\lambda\neq\lambda\beta$. Hence $\mu = \lambda\beta^{-1}\neq\lambda$. Moreover, $\lambda = \mu\beta$ and then $\mu\in N^-(\lambda)$. Clearly, $\varphi(\mu) = \varphi(\lambda\beta^{-1}) = \beta\sim_\lambda$. Consequently, $\varphi$ is a bijection. This implies that $d^-(\lambda) = |N^-(\lambda)| = \left|A_\lambda / \sim_\lambda\right|$. □

To illustrate more clearly, we present the following example for illustrating the above theorem.

Example 5.5. Let $X = \{1, 2, \ldots, 8\}$ and $Y = \{1, 2, 3\}$. Further, let $A = \{\alpha_1, \alpha_2, \alpha_3, \alpha_4\}$ be a connection set of $\Gamma$ contained in $H_{id_X}\backslash\{id_X\}$ such that

Then $Fix(\alpha_1) = Y\cup\{4, 8\}, Fix(\alpha_2) = Y\cup\{6\}, Fix(\alpha_3) = Y\cup\{5, 6\}, Fix(\alpha_4) = Y\cup\{6, 7, 8\}$ and thus $\mathop{\bigcap}\limits_{\alpha\in A}{Fix(\alpha)} = Y$. By Theorem 5.2, we have $N^-(\lambda)\neq\emptyset$ for all $\lambda\in G$. Let $\lambda\in G$ be defined as follows:

We obtain that $A_\lambda = \{\alpha\in A : X\lambda\nsubseteq Fix(\alpha)\} = \{\alpha_1, \alpha_2, \alpha_4\}$. By the equivalence relation $\sim_\lambda$ on $A_\lambda$ defined in (5.1), we obtain that $\alpha_1\sim_\lambda = \{\alpha_1\}$ and $\alpha_2\sim_\lambda = \{\alpha_2, \alpha_4\}$. Let $\mu_1, \mu_2\in G$ be defined as follows:

It is not hard to verify that the following statements hold in $\Gamma[G]$. Let $\beta\in G$.

(i) $\beta\alpha_1 = \lambda$ if and only if $\beta = \mu_1$.

(ii) $\beta\alpha_2 = \lambda$ if and only if $\beta = \mu_2$.

(iii) $\beta\alpha_3 = \lambda$ if and only if $\beta = \lambda$.

(iv) $\beta\alpha_4 = \lambda$ if and only if $\beta = \mu_2$.

Thus the subdigraph of $\Gamma[G]$ induced by $N^-[\lambda]$ is shown in Figure 1.

Hence we get that $N^-(\lambda) = \{\mu_1, \mu_2\}$. Therefore, $d^-(\lambda) = |N^-(\lambda)| = 2 = |\{\alpha_1\sim_\lambda, \alpha_2\sim_\lambda\}| = \left|A_\lambda / \sim_\lambda\right|$.

We now define certain graphical terminologies. The induced subdigraph $\Gamma[G]$ of $\Gamma$ is said to be semi-regular if $d^-(\alpha) = d^-(\beta)$ for all $\alpha, \beta\in G$. Moreover, if $d^-(\alpha) = k$ for all $\alpha\in G$, then $\Gamma[G]$ is said to be $k$-semi-regular. We now present a characterization of the semi-regularity of $\Gamma[G]$ as follows.

Theorem 5.6. Let $A\subseteq H_{id_X}\backslash\{id_X\}$ be a connection set of $\Gamma$ such that $Fix(\alpha) = Y$ for all $\alpha\in A$. The following statements are equivalent.

(i) $\Gamma[G]$ is semi-regular.

(ii) For each $x\in X\backslash Y, \, x\alpha\neq x\beta$ for all $\alpha\neq\beta\in A$.

(iii) $\sim_\lambda = 1_{A}$ for all $\lambda\in G$.

Proof. (ⅰ)$\Rightarrow$(ⅱ): Assume that $\Gamma[G]$ is semi-regular. Let $z\in X\backslash Y$ be fixed. Suppose to the contrary that there exist two distinct $\alpha, \beta\in A$ such that $z\alpha = z\beta$. Let $y\in Y$. Define $\lambda\in G$ by

We claim that $d^-(\lambda) < |A|$. If $\lambda\xi^{-1} = \lambda$ for some $\xi\in A$, then $\lambda = \lambda\xi$. Hence $(z\alpha)\xi = (z\lambda)\xi = z\lambda\xi = z\lambda = z\alpha$ which implies that $z\alpha\in Fix(\xi)$. Since $z\in X\backslash Y$ and $\alpha$ is a permutation, we have $z\alpha\in X\backslash Y$ which contradicts the assumption. So we conclude that $N^-(\lambda) = \{\lambda\xi^{-1} : \xi\in A\}$. Thus $d^-(\lambda) = |N^-(\lambda)|\leq|A|$. Now, we define $\mu\in G$ by

Therefore, $\mu\alpha = \lambda = \mu\beta$. Since $\alpha, \beta\in A$ and $Fix(\alpha) = Y = Fix(\beta)$, we have $z\alpha = z\beta\neq z$ which yields that $\mu\neq\lambda$. Furthermore, we see that $\lambda\alpha^{-1} = \mu = \lambda\beta^{-1}$. This implies that $d^-(\lambda) < |A|$, immediately. Next, we define $\eta\in G$ by

We show that $d^-(\eta) = |A|$. Indeed, $N^-(\eta) = \{\eta\xi^{-1} : \xi\in A\}$. Suppose that there exist $\xi_1, \xi_2\in A$ such that $\eta\xi^{-1}_1 = \eta\xi^{-1}_2$. For each $x\in X\backslash\{z\}$, we obtain that $x\xi^{-1}_1 = (x\eta)\xi^{-1}_1 = x(\eta\xi^{-1}_1) = x(\eta\xi^{-1}_2) = (x\eta)\xi^{-1}_2 = x\xi^{-1}_2$. Moreover, we can conclude that $z\xi^{-1}_1 = z\xi^{-1}_2$ since $\xi_1, \xi_2$ are permutations. Consequently, $\xi^{-1}_1 = \xi^{-1}_2$ and hence $\xi_1 = \xi_2$. Thus all elements in $N^-(\eta)$ are distinct which leads to $d^-(\eta) = |N^-(\eta)| = |A|$. Now, we see that $d^-(\lambda) < |A| = d^-(\eta)$ which contradicts the semi-regularity of $\Gamma[G]$.

(ⅱ)$\Rightarrow$(ⅲ): Assume that the condition holds. Let $\lambda\in G$. Since $Fix(\alpha) = Y$ for all $\alpha\in A$, we have $X\lambda\nsubseteq Fix(\alpha)$ for all $\alpha\in A$. This implies that $A_\lambda = \{\alpha\in A : X\lambda\nsubseteq Fix(\alpha)\} = A$. Clearly, $1_A = 1_{A_\lambda}\subseteq\, \, \sim_\lambda$. Next, let $\alpha, \beta\in A_\lambda$ be such that $\alpha\sim_\lambda\beta$. Since $\lambda\in G$, there exists $x\lambda\in X\backslash Y$ for some $x\in X\backslash Y$. Hence $x\in (X\backslash Y)\lambda^{-1}$. From $\alpha\sim_\lambda\beta$, we get that $x\lambda\alpha^{-1} = x\lambda\beta^{-1}\in X\backslash Y$. If $\alpha\neq\beta$, then $(x\lambda\alpha^{-1})\alpha = x\lambda(\alpha^{-1}\alpha) = x\lambda = x\lambda(\beta^{-1}\beta) = (x\lambda\beta^{-1})\beta$ contradicts the assumption. Therefore, $\alpha = \beta$ and thus $\sim_\lambda\subseteq 1_{A_\lambda} = 1_A$. Consequently, $\sim_\lambda = 1_A$, as required.

(ⅲ)$\Rightarrow$(ⅰ): Assume that the condition holds. We prove that $\Gamma[G]$ is semi-regular. Let $\lambda\in G$. By Theorem 5.4 and we have known that $A_\lambda = A$, it follows that

Hence each element in $G$ has an in-degree $|A|$. Consequently, $\Gamma[G]$ is semi-regular. □

Remark 5.7. By the proof of (iii)$\Rightarrow$(i) in Theorem 5.6, we observe that $\Gamma[G]$ is $|A|$-semi-regular.

Theorem 5.8. Let $A\subseteq H_{id_X}\backslash\{id_X\}$ be a connection set of $\Gamma$ such that $\mathop{\bigcap}\limits_{\alpha\in A}{Fix(\alpha)} = Y$. Then

where $m = \min\left\{ \left|A_\lambda / \sim_\lambda \right| : \lambda\in G\right\}$. The equality holds if $\Gamma[G]$ is semi-regular.

Proof. By Theorem 5.2, the fractional total domination number of $\Gamma[G]$ exists and then $N^-(\lambda)\neq\emptyset$ for all $\lambda\in G$. We first prove the lower bound of $\gamma^*_t(\Gamma[G])$. Let $f$ be a fractional total dominating function of $\Gamma[G]$. Then $f(N^-(\lambda))\geq 1$ for all $\lambda\in G$. We obtain that

By Lemma 4.4, we have $\Delta^+(\Gamma[G]) = |A|$. Hence

that is, $|f| = \mathop{\sum}\limits_{\mu\in G}{f(\mu)}\geq \dfrac{|G|}{|A|}$. Since $f$ is arbitrary, we conclude that

For proving the upper bound of $\gamma^*_t(\Gamma[G])$, we let $m = \min\left\{ \left|A_\lambda / \sim_\lambda \right| : \lambda\in G\right\}$ and define a function $f:G\to[0, 1]$ by $f(\lambda) = \dfrac{1}{m}$ for all $\lambda\in G$. By Theorem 5.4, we obtain that $m$ is the minimum in-degree of $\Gamma[G]$. Therefore, it is clear that $f$ is a fractional total dominating function of $\Gamma[G]$. We conclude that

We now assume that $\Gamma[G]$ is semi-regular. By Remark 5.7, we obtain that $m = |A|$. Therefore, $\gamma^*_t(\Gamma[G]) = \dfrac{|G|}{|A|}$. The equality is attained. □

6.   Conclusions

In this paper, the concepts of fractional domination and fractional total domination have been investigated for Cayley digraphs $\Gamma$ of transformation semigroups with fixed sets. The results have been divided into two major parts. The first one is related to the fractional (total) domination numbers of $\Gamma$ with respect to minimal idempotents, which is presented in Section 3. In this part, we have found that the fractional domination number and the domination number coincide. However, the fractional total domination number of $\Gamma$ does not exist. For the second part, including Sections 4 and 5, the fractional domination and fractional total domination numbers have been provided with respect to permutations. The results have been presented by considering the induced subdigraphs of $\Gamma$, separately. Further, we have introduced an equivalence relation for applying to study the fractional total domination number of certain induced subdigraph of $\Gamma$.

Use of AI tools declaration

The authors declare that they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The authors would like to thank Khon Kaen University and Rajamangala University of Technology Lanna. The first author also thanks Assoc. Prof. Dr. Kittikorn Nakprasit for his corrections and suggestions. This work was financially supported by Office of the Permanent Secretary, Ministry of Higher Education, Science, Research and Innovation, Grant No. RGNS 65-050.

Conflict of interest

No conflicts of interest exists. We wish to confirm that there are no known conflicts of interest associated with this publication and there has been no significant financial support for this work that could have influenced its outcome.