Perfect directed codes in Cayley digraphs

1.   Introduction

In this paper, we assume all digraphs considered here are simple digraphs without loops and multiple arcs between any two vertices. Moreover, the digraphs may not be connected. One may refer to [8] for basic definitions and well-known terminologies. Let ${\varGamma}$ be a connected finite digraph with a vertex set $V({\varGamma})$ and an arc set $A({\varGamma})$. The ends $u$ and $v$ of an arc $(u, v)$ are called the tail and the head of this arc, respectively. A subset S of $V({\varGamma})$ is called independent if, for any $u, v\in S$, $(u, v)\notin A({\varGamma})$. An independent subset $S$ of $V({\varGamma})$ is called a perfect kernel of ${\varGamma}$ if for each $v\in V({\varGamma})\setminus S$ there exists a unique element $x\in S$ such that $(v, x)\in A({\varGamma})$, while $S$ is called a perfect solution of ${\varGamma}$ if for each $w\in V({\varGamma})\setminus S$ there exists a unique element $y\in S$ such that $(y, w)\in A({\varGamma})$. With these terminologies, a perfect directed code (also known as efficient twin domination) of ${\varGamma}$ is a subset $S$ of $V({\varGamma})$, which is both a perfect kernel and a perfect solution.

The results about perfect directed codes (or twin domination sets) are not as fruitful as those in graphs. One may refer to [1,2,3,4,5,8,9,10,16,17] for some general results. The perfect directed codes of a digraph play an important role in solving the resource location problem and the facility location problem [12,14]. This paper is also motivated by [13].

Let $G$ be a group and $X = \{x_{1}, x_{2}, \ldots, x_{n}\}$ with $1_G\notin X$ be a subset of $G$. The Cayley digraph ${\varGamma} = {{\rm{Cay }}}(G, X)$ is defined to have a vertex set $G$ and arcs $(g, xg)$ for each $g\in G$ and $x\in X$. If $X = X^{-1}$, then it is a Cayley graph. The identity is usually excluded from $X$ in order to avoid loops. The digraph ${{\rm{Cay }}}(G, X)$ is connected if and only if $X$ generates $G$. An automorphism of ${{\rm{Cay }}}(G, X)$ refers to a bijection $\sigma$ on $G$ such that $(u, v)$ is an arc if and only if $(\sigma(u), \sigma(v))$ is an arc. Take an element $g\in G$ and define $R_g: G\rightarrow G$ as $R_g(u) = ug$ for each element $u\in G$. Then, $R_g$ is an automorphism of ${{\rm{Cay }}}(G, X)$, because $R_g$ is clearly a bijection on $G$, and $(u, v)$ is an arc if and only if $(ug, vg)$ is an arc. Some useful digraphs are Cayley digraphs; see [18,19].

Let ${\varGamma}$ and $\overline{{\varGamma}}$ be digraphs, and $\gamma:{\varGamma}\rightarrow \overline{{\varGamma}}$ be a homomorphism that maps vertices to vertices, arcs to arcs, and preserves incidences (heads to heads and tails to tails). The homomorphism $\gamma$ is called a $k$-fold covering map and ${\varGamma}$ is called a $k$-fold cover of $\overline{{\varGamma}}$ (or ${\varGamma}$ covers $\overline{{\varGamma}}$) if every vertex and arc of $\overline{{\varGamma}}$ has precisely $k$ preimages, and for every $x\in V({\varGamma})$, both the out-degree and the in-degree of $x$ are equal to the corresponding out and in degrees of $\gamma(x)$. Moreover, $\gamma$ is also called a covering map. Usually, the preimage set in ${\varGamma}$ of a vertex or an arc of $\overline{{\varGamma}}$ is called the fibre of this vertex or this arc, respectively.

In Section 2, we show that a digraph covers a complete digraph if and only if the vertex set of this digraph can be partitioned into perfect directed codes. Equivalent conditions for a subset to be a perfect directed code in Cayley digraphs are given in Section 3. And in Section 4, we give equivalent conditions for normal subsets, normal subgroups, and subgroups to be perfect directed codes of Cayley digraphs.

2.   Perfect directed codes and coverings

Let ${\varGamma}$ be a digraph, and $S_1$ and $S_2$ be two disjoint independent subsets of $V({\varGamma})$ with $|S_1| = |S_2|$. The subgraph of ${\varGamma}$ induced by $S_1\cup S_2$ is called a dimatching if for every vertex $u_1\in S_1$ there is exactly one vertex $v_2\in S_2$ and one vertex $w_2\in S_2$ ($v_2$ and $w_2$ may be the same vertex) such that $(u_1, v_2)$ and $(w_2, u_1)$ belong to $A({\varGamma})$, and vice versa for every vertex in $S_2$. From its definition, a dimatching includes several directed cycles of even lengths. The set of arcs from $S_1$ to $S_2$ involves arcs whose tails and heads are in $S_1$ and $S_2$, respectively. A complete digraph on $n$ vertices, denoted by $DK_n$, is a digraph on $n$ vertices such that there are exactly two arcs $(u, v)$ and $(v, u)$ between any two vertices $u$ and $v$.

Lemma 2.1. (1) The perfect directed codes of a digraph have equal size. Moreover, the subgraph induced by two disjoint perfect directed codes is a dimatching.

(2) Let $S_{1}, S_{2}, \ldots, S_{n}$ be $n$ perfect directed codes of a digraph ${\varGamma}$ that are pairwise mutually disjoint. Then, the subgraph induced by $\cup_{i = 1}^{n}S_{i}$ is an $m$-fold cover of the complete digraph $DK_{n}$, where $m = |S_{i}|$ for each $1\leq i\leq n$.

Proof: (1) Let $S_1$ and $S_2$ be two perfect directed codes of a digraph ${\varGamma}$, and let $S = S_1\cap S_2$. Let $|S_1| = 1$. Assume that $|S_2| \ge 2$. Let $u\in S_1$ and $v, w\in S_2$, $v \ne w$. Then we have $(u, v)$ and $(u, w)$ are arcs of these digraphs ($S_1$ is a perfect solution), which contradicts that $S_2$ is a perfect kernel. So $|S_2| = 1$ and $|S_1| = |S_2|$. Now suppose that $|S_{1}|\geq2$. Note that a perfect directed code is an independent subset. For every two distinct vertices $u_1$ and $u_2$ in $S_1$, there are vertices $v_1$ and $v_2$ in $S_2$ such that $(u_1, v_1)$ and $(u_2, v_2)$ belong to $A({\varGamma})$ because $S_2$ is a perfect directed code. Because $S_1$ is also a perfect directed code, $v_1$ and $v_2$ are distinct as well. Thus, $|S_{1}| = |S_{2}|$. Moreover, the subgraph induced by $(S_1\cup S_2)\setminus S$ is a dimatching because a perfect directed code is both a perfect kernel and a perfect solution. As a result, the subgraph induced by two disjoint perfect directed codes is a dimatching.

(2) Let $\Sigma$ be the induced subgraph in ${\varGamma}$ with $V(\Sigma) = \cup_{i = 1}^{n}S_{i}$. A dimatching is clearly a covering of $DK_2$, with each part of the vertices covering a vertex in $DK_2$. Denote the vertices of $DK_n$ by $1, 2, \ldots, n$. According to the result in (1), the subgraph induced by any two sets in $\{S_i\ |\ 1\leq i\leq n\}$ is a dimatching. As a result, $\Sigma$ is an $m$-fold cover of $DK_n$, with the vertices in $S_i$ covering the vertex $i$ of $DK_n$ and the arcs from $S_i$ to $S_j$ covering the arc from $i$ to $j$.□

Lemma 2.2. Let ${\varGamma}$ and $\overline{{\varGamma}}$ be digraphs, $\gamma:{\varGamma}\rightarrow \overline{{\varGamma}}$ be a $k$-fold covering map, $\overline{S}\subseteq V(\overline{{\varGamma}})$ and $S = \gamma^{-1}(\overline{S})$.

${\rm (1)}$ If $\overline{S}$ is a perfect kernel, then $S$ is a perfect kernel;

${\rm (2)}$ If $\overline{S}$ is a perfect solution, then $S$ is a perfect solution;

${\rm (3)}$ If $\overline{S}$ is a perfect directed code, then $S$ is a perfect directed code.

Proof: Because an arc $(u, v)\in A({\varGamma})$ will be mapped by $\gamma$ to an arc $(\gamma(u), \gamma(v))\in A(\overline{{\varGamma}})$, the fact that $S$ is independent, which follows from $\overline{S}$ being independent. Take an element $v\in V({\varGamma})\setminus S$ and set $\overline{v} = \gamma(v)$, then $\overline{v}\in V(\overline{{\varGamma}})\setminus\overline{S}$.

(1) If $\overline{S}$ is a perfect kernel, then there exists exactly one $\overline{s}\in \overline{S}$ such that $(\overline{v}, \overline{s})\in A(\overline{{\varGamma}})$. Since $\gamma$ is a covering map, there exists a $s\in\gamma^{-1}(\overline{s})\subseteq S$ such that $(v, s)\in A({\varGamma})$. Now we show that this element $s$ is unique from the definition of the covering. Suppose $s^{\prime}\in S$ is an element satisfying $(v, s^{\prime})\in A({\varGamma})$, then $(\overline{v}, \gamma(s^{\prime}))\in A(\overline{{\varGamma}})$. So, $\gamma(s) = \overline{s} = \gamma(s^{\prime})$, and there will be two parallel arcs from $\overline{v}$ to $\overline{s}$ if $s\neq s^{\prime}$, which contradicts to the assumption of $\overline{{\varGamma}}$ being simple. Consequently, $S$ is a perfect kernel of ${\varGamma}$.

(2) can be proved similarly, and (3) follows directly from (1) and (2). □

Theorem 2.3. A digraph ${\varGamma}$ covers the complete digraph $DK_{n}$ if and only if ${\varGamma}$ has a vertex partition $S_{1}, S_{2}, \ldots, S_{n}$ such that $S_{i}, 1\leq i\leq n$, are perfect directed codes of ${\varGamma}$.

Proof: The sufficiency follows from Lemma 2.1. For the necessity, let $\gamma:{\varGamma}\rightarrow DK_{n}$ be a covering map, and let $V(DK_{n}) = \{1, 2, \ldots, n\}$. Set $S_i = \gamma^{-1}(i)$. Clearly, the $n$-subsets $S_{1}, S_{2}, \ldots, S_{n}$ form a vertex partition of ${\varGamma}$. Note that $\{i\}$ is a perfect directed code of $DK_{n}$ for each $1\leq i\leq n$, so $S_{i}$ is a perfect directed code of ${\varGamma}$ according to Lemma 2.2. □

Example 2.4. Let ${\varGamma}$ be the digraph $($left$)$ in Figure 1. Set $S_1 = \{1, 2\}, S_2 = \{3, 4\}$ and $S_3 = \{5, 6\}$. Then $S_i$ is a perfect directed code of ${\varGamma}$ for each $i\in \{1, 2, 3\}$. Moreover, ${\varGamma}$ is a cover of the complete digraph $DK_3$ $($right$)$.

3.   Perfect directed codes in Cayley digraphs

In this section, we characterize perfect directed codes in Cayley digraphs. For any two subsets $U, V$ of $G$, set $UV = \{uv\ |\ u\in U, v\in V\}$. If $U = \emptyset$ or $V = \emptyset$, then set $UV = \emptyset$. In particular, if $U = \{u\}$, then we denote $UV$ by $uV$; if $V = \{v\}$, then we denote $UV$ by $Uv$, .

Lemma 3.1. Let ${{\rm{Cay }}}(G, X)$ be a Cayley digraph of a group $G$ for some $X = \{x_{1}, x_{2}, \ldots, x_{n}\}$ with $1_G\notin X$, and let $S$ be a subset of $G$. Suppose that $g\in G$.

(1) The following are equivalent:

${\rm (a)}$ $S$ is a perfect solution;

${\rm (b)}$ $Sg$ is a perfect solution;

${\rm (c)}$ The $|X|+1$ subsets, $xS, x\in X\cup \{1_{G}\}$, form a partition of $G$.

(2) The following are equivalent:

${\rm (i)}$ $S$ is a perfect kernel;

${\rm (ii)}$ $Sg$ is a perfect kernel;

${\rm (iii)}$ The $|X|+1$ subsets, $x^{-1}S, x\in X\cup \{1_{G}\}$, form a partition of $G$.

(3) $S$ is a perfect directed code of ${{\rm{Cay }}}(G, X)$ if and only if $S$ is a perfect directed code of ${{\rm{Cay }}}(G, X^{-1})$.

Proof: If $S$ is a perfect solution (a perfect kernel), then $\varphi(S)$ is obviously a perfect solution (a perfect kernel) for each automorphism $\varphi$ of ${{\rm{Cay }}}(G, X)$. Recall that $R_g$ is an automorphism of ${\varGamma}$ for each $g\in G$, so $R_g(S) = Sg$ is a perfect solution (a perfect kernel) under the condition of $S$ being a perfect solution (a perfect kernel). Similarly, $R_{g^{-1}}(Sg) = S$ is a perfect solution (a perfect kernel) under the condition of $Sg$ being a perfect solution (a perfect kernel).

(1) Assume that $S$ is a perfect solution, then $G = S\cup x_{1}S\cup\cdots\cup x_{n}S$. Since $S$ is an independent subset, $S\cap x_{i}S = \emptyset$ for each $1\leq i\leq n$. If $x_{i}S\cap x_{j}S\neq \emptyset$ for $x_i$ and $x_j$, then $x_{i}s = x_{j}s^{\prime}$ for some vertices $s$ and $s^{\prime}$ in $S$. This implies that there are two arcs with tails $s$ and $s^{\prime}$ that have the same head. Therefore, $s = s^{\prime}$ because $S$ is a solution. As a result, $x_i = x_j$ and the $|X|+1$ subsets, $xS, x\in X\cup \{1_{G}\}$, form a partition of $G$.

For the other direction, assume that the $|X|+1$ subsets, $xS, x\in X\cup \{1_{G}\}$, form a partition of $G$. As $xS\cap S = \emptyset$ for every $x\in X$, $S$ is an independent subset. Furthermore, for every $y\in G\setminus S$, there exists a unique $x\in X$ such that $y\in xS$. That is to say, there is a unique $s\in S$ such that $(s, y)\in A({\varGamma})$. So, $S$ is a perfect solution.

(2) Note that if $S$ is a perfect kernel, then $G = S\cup x_{1}^{-1}S\cup\cdots\cup x_{n}^{-1}S$. The equivalence of $S$ being a perfect kernel and the partition of $G$ by the $|X|+1$ subsets, $x^{-1}S, x\in X\cup \{1_{G}\}$, can be shown in a quite similar way. It is clear that (3) can be inferred directly from (1) and (2). □

Remark 3.2. ${{\rm{Cay}}}(G, X)$ may not be connected in Lemma 3.1.

Note that a perfect solution of a digraph may not be the perfect kernel of this digraph, and vice versa.

Example 3.3. Let $D_6 = \{ a, b\ |\ a^3 = b^2 = 1, b^{-1}ab = a^{-1}\}$ be the dihedral group of order $6$. Take $X = S_1 = \{a, b\}, S_2 = \{a, ba^2\}$. Then, $S_1$ is a perfect solution but not a perfect kernel of ${\varGamma} = {{\rm{Cay }}}(D_6, X)$, while $S_2$ is a perfect kernel of ${\varGamma}$ but not a perfect solution. In fact, it is easy to see in Figure 2 that ${\varGamma}$ does not have perfect directed codes.

Let $G$ be a group and $S$ be a subset of $G$. If $Sg = gS$ for every $g\in G$, then $S$ is called a normal subset of $G$. It is obvious that $S$ is normal if and only if $Sx = xS$ for every $x\in X$ when $X$ generates $G$.

Corollary 3.4. Let ${\varGamma} = {{\rm{Cay }}}(G, X)$ be a Cayley digraph of a group $G$, and let $S$ be a perfect directed code of ${\varGamma}$. If $S$ is a normal subset of $G$, then there exists a covering map ${\gamma}:{\varGamma}\rightarrow DK_{|X|+1}$ such that $\{Sx {\bigm|} x\in X\cup \{1_G\}\}$ are the fibres of vertices in $DK_{|X|+1}$.

Proof: According to Lemma 3.1, the $|X|+1$ subsets, $S, xS = Sx, x\in X$, are mutually disjoint perfect directed codes. So, according to Theorem 2.3, ${\varGamma}$ covers $DK_{|X|+1}$ with $Sx, x\in X\cup \{1_G\}$, as the fibres of vertices in $DK_{|X|+1}$. □

Theorem 3.5. Let $G$ be a finite group, ${\varGamma} = {{\rm{Cay }}}(G, X)$ be a Cayley digraph with $X = \{x_{1}, x_{2}, \ldots, x_{n}\}$, and $S$ be a normal subset of $G$. The following items are equivalent.

${\rm (1)}$ $S$ is a perfect directed code of ${\varGamma}$;

${\rm (2)}$ There exists a covering map $\gamma:{\varGamma}\rightarrow DK_{n+1}$ such that $\gamma^{-1}(v) = S$ for some $v\in V(DK_{n+1})$;

${\rm (3)}$ $|S| = \frac{|G|}{n+1}$ and $S(X\cup ((X^{-1}X)\setminus \{1_{G}\}))\cap S = \emptyset$;

${\rm (4)}$ The $n+1$ subsets, $Sx, x\in X\cup\{1_{G}\},$ form a partition of $V({\varGamma})$.

Proof: Because $S$ is a normal subset of $G$, $Sg = gS$ for every $g\in G$, and the fact that (1) and (2) are equivalent is obvious according to Theorem 2.3 and Corollary 3.4.

$(1)\Rightarrow (3)$ By Lemma 3.1, the subsets $xS, x\in X\cup\{1_{G}\},$ form a vertex partition of ${\varGamma}$. So, $|S| = \frac{|G|}{n+1}$ and $Sx_i\cap S = \emptyset$ for each $x_{i}\in X$.

Suppose $S(X^{-1}X\setminus\{1_{G}\})\cap S\neq\emptyset$, then there exist $s_{1}, s_{2}\in S$, $x_{1}, x_{2}\in X$ and $x_{1}\neq x_{2}$ such that $x_{2}^{-1}x_{1}s_1 = s_{2}$, i.e., $x_1s_1 = x_2s_2$. This contradicts $x_1S\cap x_2S = \emptyset$.

$(3)\Rightarrow (4)$ Since $(X\cup X^{-1}X\setminus \{1_{G}\})S\cap S = \emptyset$, for each $x_{i}\in X$, $x_{i}S\cap S = \emptyset$, i.e., $Sx_{i}\cap S = \emptyset$, and for any two different elements $x_{i}, x_{j}\in X$, $x_{i}^{-1}x_{j}S\cap S = \emptyset$, i.e., $x_{j}S\cap x_{i}S = \emptyset$, that is $Sx_{j}\cap Sx_{i} = \emptyset$. Furthermore, the condition $|S| = \frac{|G|}{n+1}$ implies $G = S\cup Sx_{1}\cup\cdots\cup Sx_{n}$.

$(4)\Rightarrow (1)$ Since the $|X|+1$ subsets, $xS, x\in X\cup\{1_{G}\}$, form a vertex partition of ${\varGamma}$, $S$ is a perfect solution according to Lemma 3.1.

For any two different elements $x_i$ and $x_j$ in $X$, $x_{i}S\cap x_{j}S = \emptyset$ is equivalent to $x_{j}^{-1}x_{i}S\cap S = \emptyset$, which is $Sx_{j}^{-1}x_{i}\cap S = \emptyset$, and so $Sx_{j}^{-1}\cap Sx_{i}^{-1} = \emptyset$. Hence, $Sx^{-1} = x^{-1}S, x\in X\cup\{1_{G}\}$, also form a vertex partition of ${\varGamma}$. So, $S$ is a perfect kernel of ${\varGamma}$. □

Example 3.6. Let $G = \mathbb{Z}_p^n$ be the $n$-times direct product group of $\mathbb{Z}_p$, where $p$ is an odd prime number. Let $X = \{e_1, e_2, \ldots, e_n\}$, where $e_i = (0, \ldots, 1, \ldots, 0)\in G$ has exactly a '1' at the $i$-th coordinate. Then, ${{\rm{Cay }}}(G, X)$ has a perfect directed code if and only if $n = p^m-1$ for some positive integer $m$.

Proof: Clearly, ${{\rm{Cay }}}(G, X)$ is a connected Cayley digraph, and each vertex has both out and in degree $n$.

On the one side, by Theorem 3.5, if ${{\rm{Cay }}}(G, X)$ has a perfect directed code $H$, then the subsets, $H, H+e_1, \cdots, H+e_n$, form a partition of $G$. So, $p^n = |G| = |H|(n+1)$, and $n = p^m-1$ for some positive integer $m$.

On the other side, assume $n = p^m-1$ for some positive integer $m$. Denote the vector space of dimension $m$ on the finite field $F_p$ with $p$ elements as $F_p^m$. Construct an $n\times m$-matrix $A$: the rows of $A$ are all non-zero vectors in $F_p^m$. Because the rank of $A$ is $m$, all solutions of $\zeta A = \mathbf{0}$ where $\zeta$ is a vector constitute a $(n-m)$-dimension subspace $T$ of $F_p^n$.

We claim that $T$ is a perfect directed code of ${{\rm{Cay }}}(G, X)$.

Now we show that $T$ is an independent subset. Otherwise, there exist two different vectors $\alpha$ and $\beta$ in $T$ such that $e_i = \alpha-\beta\in X$ for some $1\leq i\leq n$. It follows that $e_iA = \mathbf{0}$. Note that $\mathbf{0} = e_iA$ is the $i$-th row of $A$. Then the $i$-th row of $A$ is a zero vector, contradicting the construction of $A$. So, $T$ is an independent subset.

Note that the elements of $G$ can be identified with the vectors in $F_p^n$. For each $\delta\in G\setminus T$, suppose there are two different vectors $\alpha$ and $\beta$ in $T$ such that $\delta = \alpha+e_i = \beta+e_j$ for $1\leq i\neq j\leq n$, then $(e_i-e_j)A = \mathbf{0}$, which implies that $A$ has two equal rows, also a contradiction. Similarly, there is at most one vector $\eta$ in $T$ satisfying $\delta+e_k = \eta$ for some $1\leq k\leq n$. Considering $|T|(n+1) = p^n$, both $T, T+e_1, \ldots, T+e_n$ and $T, T-e_1, \ldots, T-e_n$ are partitions of $G$. By Theorem 3.4, $T$ is a perfect directed code. □

Remark 3.7. For $p = 2$ in Example 3.6, ${{\rm{Cay }}}(G, X)$ is the hypercube $Q_n$. Moreover, $Q_n$ has a Hamming code (or perfect directed code) if and only if $n = 2^m-1$ for a positive integer $m$, see [13].

4.   Perfect directed coding subgroup

Let $G$ be a finite group and ${{\rm{Cay }}}(G, X)$ be a Cayley digraph of degree $n$, which admits a perfect directed code $C$. Assume $X = \{x_1, \ldots, x_{n}\}$. Then, according to Lemma 3.1, both the $n+1$ subsets, $C, x_rC, 1\leq r\leq n$, and $C, x_s^{-1}C, 1\leq s\leq n$, form partitions of $G$. So, $|G| = (n+1)|C|$, and $|C|$ is a factor of $|G|$. Let $H$ be a subgroup of $G$. Because $|H|$ is a factor of $|G|$, a natural question is: under what conditions can $H$ be a perfect directed code?

The elements of $G$ can be partitioned by $H$ into $m = \frac{|G|}{|H|}$ disjoint subsets $Hv_i, 1\leq i\leq m$, by the equivalent relation of two elements $x$ and $y$ in $G$ being equivalent if and only if $xy^{-1}\in H$. In group theory, $Hv_i$ is called a right coset of $H$ in $G$, $v_i\in G$ a representative element of this coset, and $\{v_1, v_2, \ldots, v_{m}\}$ a right transversal of $H$ in $G$. Similarly, $G$ can also be partitioned into $m$ subsets, $u_iH, 1\leq i\leq m$, by the equivalent relation of two elements $x$ and $y$ in $G$ being equivalent if and only if $y^{-1}x\in H$. And, $u_iH$ is called a left coset of $H$ in $G$, $u_i\in G$ is a representative element of this coset; and $\{u_1, u_2, \ldots, u_{m}\}$ a left transversal of $H$ in $G$. Because $H$ itself is both a right and a left coset, each right and left transversal of $H$ consists of exactly one element from $H$. A set is called a transversal of $H$ if it is both a right transversal and a left transversal of $H$. A normal subgroup $N$ of a group $G$ refers to a subgroup $N$ satisfying $Ny = yN$ for every $y\in G$. So, one does not need to distinguish between the left and right cosets of normal subgroups.

Corollary 4.1. Let ${\varGamma} = {{\rm{Cay }}}(G, X)$ be a digraph with $X = \{x_{1}, x_{2}, \ldots, x_{n}\}$, and let $H$ be a normal subgroup of $G$. The following items are equivalent.

${\rm (1)}$ $H$ is a perfect directed code of ${\varGamma}$;

${\rm (2)}$ There exists a covering map $\gamma:{\varGamma}\rightarrow DK_{n+1}$ such that $\gamma^{-1}(v) = H$ for some $v\in V(DK_{n+1})$;

${\rm (3)}$ $|H| = \frac{|G|}{n+1}$ and $(X\cup X^{-1}X)\cap H = \{1_{G}\}$;

${\rm (4)}$ $X\cup\{1_{G}\}$ is a transversal of $H$ in $G$.

Proof: Firstly, we want to show that the condition $H(X\cup X^{-1}X\setminus \{1_{G}\})\cap H = \emptyset$ is equivalent to that of $(X\cup X^{-1}X)\cap H = \{1_G\}$.

Assume $H(X\cup X^{-1}X\setminus \{1_{G}\})\cap H = \emptyset$, then $(X\cup X^{-1}X\setminus \{1_{G}\})\cap H = \emptyset$ and so $(X\cup X^{-1}X)\cap H = \{1_{G}\}$.

If $H(X\cup X^{-1}X\setminus \{1_{G}\})\cap H\neq\emptyset$, then there exist $h_{1}, h_{2}, h_3, h_4\in H$, $x_{1}, x_{2}, x_3\in X$, $x_{1}\neq x_{2}$, such that $h_{1} = h_2x_{1}^{-1}x_{2}$ or $h_3x_3 = h_4$. Then, $1_{G}\neq x_{1}^{-1}x_{2} = h_{2}^{-1}h_{1}\in H$ or $x_3 = h_3^{-1}h_4\in H$. Therefore, $(X\cup X^{-1}X)\cap H\neq\{1_{G}\}$.

Secondly, it is obvious that the subsets, $Hx, x\in X\cup\{1_{G}\}$, form a vertex partition of ${\varGamma}$ if and only if $X\cup\{1_{G}\}$ is a transversal of $H$ in $G$.

Thus, the four items are equivalent according to Theorem 3.5. □

Generally speaking, take a subgroup $T$ of $G$, then $Ty_1, Ty_2, \cdots, Ty_m$ may not be a partition of $G$ even if $y_1T, y_2T, \cdots, y_mT$ is a partition of $G$. But if $T$ is a perfect directed code of a Cayley digraph of $G$, then it has some similar properties to a normal subgroup.

Theorem 4.2. Let ${\varGamma} = {{\rm{Cay }}}(G, X)$ be a digraph of a group $G$ with $X = \{x_{1}, x_{2}, \ldots, x_{n}\}$, and let $T$ be a subgroup of $G$. The following items are equivalent.

${\rm (1)}$ $T$ is a perfect directed code of ${\varGamma}$;

${\rm (2)}$ There exists a covering map $\gamma:{\varGamma}\rightarrow DK_{n+1}$ such that $\gamma^{-1}(v) = T$ for some $v\in V(DK_{n+1})$;

${\rm (3)}$ $|T| = \frac{|G|}{n+1}$, $(X\cup X^{-1}X\cup XX^{-1})\cap T = \{1_{G}\}$;

${\rm (4)}$ $X\cup\{1_{G}\}$ is a transversal of $T$.

Proof: Under the condition of $T$ being a perfect directed code, the $n+1$ subsets, $T, x_1T, \ldots, x_nT,$ form a partition of $G$ according to Lemma 3.1. So, $T$ has $n+1$ left or right cosets in $G$, $X\cup\{1_{G}\}$ is a left transversal of $T$, and $|G| = |T|(n+1)$. Because $Tg$ is a perfect directed code of ${\varGamma}$ for every $g\in G$, the $n+1$ right cosets of $T$ are mutually disjoint perfect directed codes of ${\varGamma}$. According to Theorem 2.3, (1) and (2) are equivalent.

(1)$\Rightarrow$(3): Take an element $a\in (X\cup X^{-1}X\cup XX^{-1})\cap T$, then $a\in X\cap T$ or $a = x_i^{-1}x_j\in T$ or $a = x_rx_t^{-1}\in T$ for $x_i, x_j, x_r, x_t$ in $X$. Under the assumption of $T$ being a perfect directed code, for any $x, x_i, x_j\in X$ and $x_i\neq x_j$,

so $a = 1_G$.

(3)$\Rightarrow$(4): The assumption of $(X\cup X^{-1}X\cup XX^{-1})\cap T = \{1_{G}\}$ implies that $T\cap x_iT = x_iT\cap x_jT = T\cap x_i^{-1}T = x_i^{-1}T\cap x_j^{-1}T = \emptyset$ for any two different elements $x_i$ and $x_j$ in $X$. Furthermore, because $|T| = \frac{|G|}{n+1}$, both $X\cup \{1_G\}$ and $X^{-1}\cup \{1_G\}$ are left transversals of $T$.

By taking the inverse subset of $x^{-1}T$ for every $x\in X$, $T\cap Tx_i = Tx_i\cap Tx_j = \emptyset$, which follows directly from $T\cap x_i^{-1}T = x_i^{-1}T\cap x_j^{-1}T = \emptyset$ for any two different elements $x_i$ and $x_j$ in $X$. Therefore, $X\cup\{1_{G}\}$ is also a right transversal of $T$.

(4)$\Rightarrow$(1): The assumption of $X\cup\{1_{G}\}$ being both a left and a right transversal of $T$ in $G$ implies that both $T, x_{1}T, \ldots, x_{n}T$ and $T, Tx_{1}, \ldots, Tx_{n}$ are partitions of $G$. Therefore, $T, x_1^{-1}T, \ldots, x_n^{-1}T$ form a partition of $G$ as well. According to Lemma 3.1, $T$ is a perfect directed code of ${\varGamma}$. □

Remark 4.3. In Theorem 4.2, if $X = X^{-1}$, then clearly $X\cup\{1_{G}\}$ forms a left transversal if and only if it forms a right transversal. But, generally, it is common that $X$ may not be a right transversal of $T$ even if $X$ is a left transversal. As in Example 3.3, no subgroup of $D_6$ can be a perfect directed code.

Example 4.4. Let $p$ be an odd prime number and $k\geq 2$ be a factor of $p-1$. Let $G = \langle a, b\ |\ a^p = b^k = 1_G, b^{-1}ab = a^i, i^k\equiv 1\ {\rm mod}\ p\rangle$ be a split metacyclic group, which is a group of order $pk$. Take $T = \langle b\rangle$ and $T$ is not normal in $G$. Set $X = \{a^ib\ |\ 1\leq i\leq p-1\}$. Then, $X\cup \{1_G\}$ is both a left and a right transversal of $T$. So, $T$ is a perfect directed code of ${{\rm{Cay }}}(G, X)$.

According to Lemma 3.1, if a subset $C$ with $|C| = m$ is a perfect directed code of a Cayley digraph of a finite group $G$ with $|G| = n$, then $m|n$. While this condition may not be sufficient, it corresponds to a special perfect directed code if $G$ is a cyclic group.

Lemma 4.5. Let $G = \langle a\rangle$ be a cyclic group of order $n$. Then, a connected Cayley digraph ${{\rm{Cay }}}(G, X)$ of degree $m-1$ admits a perfect directed code if $m$ divides $n$ and $x_i x_j^{-1}\notin \langle a^m\rangle$ for any two distinct $x_i$ and $x_j$ in $X\cup \{1_G\}$.

Proof: Assume that $m\; |\; n$ and $x_i x_j^{-1}\notin \langle a^m\rangle$ for any two distinct $x_i$ and $x_j$ in $X\cup \{1_G\}$. Set $T = \langle a^m\rangle$. Then, under the condition of $x_i x_j^{-1}\notin T$, both the $|X|+1$ subsets, $T, x_iT, x_i\in X$, and $T, x_j^{-1}T, x_j\in X$, form partitions of $G$. So, according to Lemma 3.1, $T$ is a perfect directed code of ${{\rm{Cay }}}(G, X)$. □

Note that the condition $x_i x_j^{-1}\notin \langle a^m\rangle$ in Lemma 4.5 is not necessary, which is different from that in Cayley graphs [7].

Example 4.6. Let $G = \langle a\rangle$ be the cyclic group of order 24. Set $C = \{1_G, a^2, a^8, a^{10}, a^{16}, a^{18}\}$ and $X = \{a, a^4, a^5\}$. It is easy to check that both the 4 subsets, $C, aC, a^4C, a^5C$ and $C, a^{-1}C, a^{-4}C, a^{-5}C$ form partitions of $G$. So, $C$ is a perfect directed code of ${{\rm{Cay }}}(G, X)$.

A subgroup $T$ of $G$ is called a perfect directed coding subgroup if there exists $X\subset G$ such that $T$ is a perfect directed code of the Cayley digraph ${{\rm{Cay }}}(G, X)$, and $T$ is called a connected perfect directed coding subgroup if ${{\rm{Cay }}}(G, X)$ is connected. We will show that every subgroup of the Frattini subgroup of a finite group is a connected, perfect directed coding subgroup.

Given a group $G$, the intersection of all maximal subgroups of $G$ is called the Frattini subgroup of $G$, is denoted by $\Phi(G)$. An element $a$ of a group $G$ is called a non-generator of $G$ if, whenever the set $X$ generates $G$, then the set $X\backslash\{a\}$ also generates $G$. The following result shows that the Frattini subgroup equals the set of non-generators.

Proposition 4.7. [15, Theorem 10.12] For all finite groups $G$, the set of non-generators of $G$ equals the Frattini subgroup of $G$.

Let ${\varGamma}$ be an undirected graph, $S\subseteq V({\varGamma})$, and $N(S)$ be a set of vertices of $V({\varGamma})$ adjacent to a vertex in $S$. The following Proposition 4.8 (Hall's marriage theorem) is well known.

Proposition 4.8. [6, Ch.3.3 Theorem 7] A bipartite graph ${\varGamma}$ with vertex sets $V_1$ and $V_2$ contains a complete matching from $V_1$ to $V_2$ iff

The following Proposition 4.9 can be obtained from [11] or Proposition 4.8. Here is a short proof.

Proposition 4.9. Let $G$ be a finite group, and let $T$ be a subgroup of $G$ such that $|G:T| = n$. Then there exists $X = \{ x_1, x_2, \ldots, x_{n-1}\}\subseteq G$ such that $X\cup\{1_{G}\}$ is a transversal of $T$ in $G$.

Proof Let $\{a_1, a_2, \ldots, a_{n-1}\}\cup \{1_{G}\}$ be a left transversal of $T$ and $\{b_1, b_2, \ldots, b_{n-1}\}\cup \{1_{G}\}$ be a right transversal of $T$. Let ${\varGamma}$ be a bipartite graph with vertex sets $V_1 = \{a_iT {\bigm|} 1\le i \le n-1\}$ and $V_2 = \{Tb_i {\bigm|} 1\le i \le n-1\}$ such that $\{a_iT, Tb_j\}$ is an edge if and only if $a_iT \cap Tb_j\ne \emptyset$. Let $S$ be an arbitrary subset of $V_1$ and $S = \{g_iT {\bigm|} 1\le i \le m\}$ for some $m$. We claim that there are at least $m$ vertices in $N(S)$. Otherwise, $|\bigcup_{x\in N(S)}x| < |\bigcup_{x\in S}x| = m|T|$, which implies that there exists a vertex $Tb\notin N(S)$ adjacent to a vertex in $S$, a contradiction. So $|N(S)|\ge |S|$. By Proposition 4.8, ${\varGamma}$ contains a complete matching from $V_1$ to $V_2$. So we may assume, without loss of generality, that

is a complete matching. Chose $x_i\in a_iT\cap Tb_i$ for $1\le i \le n-1$ and let $X = \{ x_1, x_2, \ldots, x_{n-1}\}$. Then $X\cup\{1_{G}\}$ forms both a left transversal and a right transversal of $T$ in $G$, as required. □

A subgroup $H$ of $G$ is called proper if $H\ne G$. Since every proper subgroup has a transversal, we introduce the following transversal Cayley digraphs:

Definition 4.10. Let $G$ be a finite group, and let $X$ be a subset of $G$. The Cayley digraph ${{\rm{Cay }}}(G, X)$ is called a transversal Cayley digraph if $X\cup \{1_{G}\}$ is a transversal of a suitable subgroup of $G$.

By Theorem 4.2 and Proposition 4.9, we get the following theorem:

Theorem 4.11. Let $G$ be a finite group. Then every proper subgroup $H$ of $G$ is a perfect directed coding subgroup.

Proof By Proposition 4.9, there exists $X = \{ x_1, x_2, \ldots, x_{n-1}\}\subseteq G$ such that $X\cup\{1_{G}\}$ is a transversal of $H$ in $G$. By Theorem 4.2, $H$ is a perfect directed code of the transversal Cayley digraph ${{\rm{Cay }}}(G, X)$. Therefore, $H$ is a perfect directed coding subgroup. □

Corollary 4.12. Let $G$ be a finite group, and let $T$ be a subgroup of $\Phi(G)$. Then $T$ is a connected, perfect directed coding subgroup.

Proof By Theorem 4.11, we may assume that $T$ is a perfect directed code for the transversal Cayley digraph ${{\rm{Cay }}}(G, X)$. And so $G = {\langle} X, T {\rangle} = {\langle} X, \Phi(G){\rangle}$. From Proposition 4.7, we have $G = {\langle} X{\rangle}$. It follows that ${{\rm{Cay }}}(G, X)$ is connected, as desired. □

Example 4.13. Let $p$ be a prime. If $G$ is a $p$-group and $G'$ is the commutator group of $G$, then every subgroup of $\Phi(G) = G^\prime{\langle} a^p {\bigm|} a \in G {\rangle}$ is a perfect directed coding subgroup of a connected Cayley digraph.

Theorem 4.14. Every proper subgroup of a cyclic group $G$ is a perfect directed coding subgroup of a connected Cayley digraph.

Proof Let $T$ be a proper subgroup of $G = {\langle} a{\rangle}$ and $X\cup\{1_{G}\}$ be a transversal of $T$. Then we may assume $a\in X$. And so $G = {\langle} X{\rangle}$. Clearly, $T$ is a perfect directed code of the connected Cayley digraph ${{\rm{Cay }}}(G, X)$. Then $T$ is a perfect directed coding subgroup, as desired. □

Let $G = {\langle} a, b {\bigm|} a^n = b^2 = 1, a^b = a^{-1}{\rangle}$ be a dihedral group. Then ${\langle} a{\rangle}$ is not a perfect directed coding subgroup of any connected Cayley digraph, and ${\langle} b{\rangle}$ is a perfect directed coding subgroup of a connected Cayley digraph. So we propose the following open problem:

Open Problem 4.15. Characterize finite groups such that each of their proper subgroups is a perfect directed code of a connected transversal Cayley digraph.

Author contributions

Yan Wang: Conceptualization, Methodology, Validation, Writing-review and editing, Formal analysis, Supervision; Kai Yuan: Conceptualization, Investigation, Methodology, Formal analysis, Writing-review and editing; Ying Zhao: Methodology, Writing-original draft preparation, Visualization, Validation.

Use of AI tools declaration

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

Acknowledgments

The authors thank the referees for the helpful comments and suggestions. This work is supported by NSFC (No. 12101535) and NSFS (No. ZR2023MA078, ZR2020MA044).

Conflict of interest

The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.