
A perfect directed code (or an efficient twin domination) of a digraph is a vertex subset where every other vertex in the digraph has a unique in- and a unique out-neighbor in the subset. In this paper, 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 subsets in Cayley digraphs to be perfect directed codes are given. Especially, equivalent conditions for normal subsets, normal subgroups, and subgroups to be perfect directed codes in Cayley digraphs are given. Moreover, we show that every subgroup of a finite group is a perfect directed code for a transversal Cayley digraph.
Citation: Yan Wang, Kai Yuan, Ying Zhao. Perfect directed codes in Cayley digraphs[J]. AIMS Mathematics, 2024, 9(9): 23878-23889. doi: 10.3934/math.20241160
[1] | Nuttawoot Nupo, Sayan Panma . Certain structural properties for Cayley regularity graphs of semigroups and their theoretical applications. AIMS Mathematics, 2023, 8(7): 16228-16239. doi: 10.3934/math.2023830 |
[2] | Nuttawoot Nupo, Chollawat Pookpienlert . Fractional domination and fractional total domination on Cayley digraphs of transformation semigroups with fixed sets. AIMS Mathematics, 2024, 9(6): 14558-14573. doi: 10.3934/math.2024708 |
[3] | Zhihong Xie, Guoliang Hao, S. M. Sheikholeslami, Shuting Zeng . On the Italian reinforcement number of a digraph. AIMS Mathematics, 2021, 6(6): 6490-6505. doi: 10.3934/math.2021382 |
[4] | Qiuyan Wang, Weixin Liu, Jianming Wang, Yang Yan . A class of nearly optimal codebooks and their applications in strongly regular Cayley graphs. AIMS Mathematics, 2024, 9(7): 18236-18246. doi: 10.3934/math.2024890 |
[5] | Xiaoling Zhou, Chao Yang, Weihua He . The linear $ k $-arboricity of digraphs. AIMS Mathematics, 2022, 7(3): 4137-4152. doi: 10.3934/math.2022229 |
[6] | Tao Cheng, Junchao Mao . A new class of directed strongly regular Cayley graphs over dicyclic groups. AIMS Mathematics, 2024, 9(9): 24184-24192. doi: 10.3934/math.20241176 |
[7] | Xiaoling Zhou, Chao Yang, Weihua He . The linear $ k $-arboricity of symmetric directed trees. AIMS Mathematics, 2022, 7(2): 1603-1614. doi: 10.3934/math.2022093 |
[8] | Jiangmin Pan, Yingnan Zhang . On cubic semisymmetric bi-Cayley graphs on nonabelian simple groups. AIMS Mathematics, 2022, 7(7): 12689-12701. doi: 10.3934/math.2022702 |
[9] | M. Haris Mateen, Muhammad Khalid Mahmmod, Dilshad Alghazzawi, Jia-Bao Liu . Structures of power digraphs over the congruence equation $ x^p\equiv y\; (\text{mod}\; m) $ and enumerations. AIMS Mathematics, 2021, 6(5): 4581-4596. doi: 10.3934/math.2021270 |
[10] | Bana Al Subaiei, Ahlam AlMulhim, Abolape Deborah Akwu . Vertex-edge perfect Roman domination number. AIMS Mathematics, 2023, 8(9): 21472-21483. doi: 10.3934/math.20231094 |
A perfect directed code (or an efficient twin domination) of a digraph is a vertex subset where every other vertex in the digraph has a unique in- and a unique out-neighbor in the subset. In this paper, 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 subsets in Cayley digraphs to be perfect directed codes are given. Especially, equivalent conditions for normal subsets, normal subgroups, and subgroups to be perfect directed codes in Cayley digraphs are given. Moreover, we show that every subgroup of a finite group is a perfect directed code for a transversal Cayley digraph.
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 Γ be a connected finite digraph with a vertex set V(Γ) and an arc set A(Γ). 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(Γ) is called independent if, for any u,v∈S, (u,v)∉A(Γ). An independent subset S of V(Γ) is called a perfect kernel of Γ if for each v∈V(Γ)∖S there exists a unique element x∈S such that (v,x)∈A(Γ), while S is called a perfect solution of Γ if for each w∈V(Γ)∖S there exists a unique element y∈S such that (y,w)∈A(Γ). With these terminologies, a perfect directed code (also known as efficient twin domination) of Γ is a subset S of V(Γ), 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={x1,x2,…,xn} with 1G∉X be a subset of G. The Cayley digraph Γ=Cay(G,X) is defined to have a vertex set G and arcs (g,xg) for each g∈G and x∈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 Cay(G,X) is connected if and only if X generates G. An automorphism of Cay(G,X) refers to a bijection σ on G such that (u,v) is an arc if and only if (σ(u),σ(v)) is an arc. Take an element g∈G and define Rg:G→G as Rg(u)=ug for each element u∈G. Then, Rg is an automorphism of Cay(G,X), because Rg 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 Γ and ¯Γ be digraphs, and γ:Γ→¯Γ be a homomorphism that maps vertices to vertices, arcs to arcs, and preserves incidences (heads to heads and tails to tails). The homomorphism γ is called a k-fold covering map and Γ is called a k-fold cover of ¯Γ (or Γ covers ¯Γ) if every vertex and arc of ¯Γ has precisely k preimages, and for every x∈V(Γ), both the out-degree and the in-degree of x are equal to the corresponding out and in degrees of γ(x). Moreover, γ is also called a covering map. Usually, the preimage set in Γ of a vertex or an arc of ¯Γ 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.
Let Γ be a digraph, and S1 and S2 be two disjoint independent subsets of V(Γ) with |S1|=|S2|. The subgraph of Γ induced by S1∪S2 is called a dimatching if for every vertex u1∈S1 there is exactly one vertex v2∈S2 and one vertex w2∈S2 (v2 and w2 may be the same vertex) such that (u1,v2) and (w2,u1) belong to A(Γ), and vice versa for every vertex in S2. From its definition, a dimatching includes several directed cycles of even lengths. The set of arcs from S1 to S2 involves arcs whose tails and heads are in S1 and S2, respectively. A complete digraph on n vertices, denoted by DKn, 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 S1,S2,…,Sn be n perfect directed codes of a digraph Γ that are pairwise mutually disjoint. Then, the subgraph induced by ∪ni=1Si is an m-fold cover of the complete digraph DKn, where m=|Si| for each 1≤i≤n.
Proof: (1) Let S1 and S2 be two perfect directed codes of a digraph Γ, and let S=S1∩S2. Let |S1|=1. Assume that |S2|≥2. Let u∈S1 and v,w∈S2, v≠w. Then we have (u,v) and (u,w) are arcs of these digraphs (S1 is a perfect solution), which contradicts that S2 is a perfect kernel. So |S2|=1 and |S1|=|S2|. Now suppose that |S1|≥2. Note that a perfect directed code is an independent subset. For every two distinct vertices u1 and u2 in S1, there are vertices v1 and v2 in S2 such that (u1,v1) and (u2,v2) belong to A(Γ) because S2 is a perfect directed code. Because S1 is also a perfect directed code, v1 and v2 are distinct as well. Thus, |S1|=|S2|. Moreover, the subgraph induced by (S1∪S2)∖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 Σ be the induced subgraph in Γ with V(Σ)=∪ni=1Si. A dimatching is clearly a covering of DK2, with each part of the vertices covering a vertex in DK2. Denote the vertices of DKn by 1,2,…,n. According to the result in (1), the subgraph induced by any two sets in {Si | 1≤i≤n} is a dimatching. As a result, Σ is an m-fold cover of DKn, with the vertices in Si covering the vertex i of DKn and the arcs from Si to Sj covering the arc from i to j.
Lemma 2.2. Let Γ and ¯Γ be digraphs, γ:Γ→¯Γ be a k-fold covering map, ¯S⊆V(¯Γ) and S=γ−1(¯S).
(1) If ¯S is a perfect kernel, then S is a perfect kernel;
(2) If ¯S is a perfect solution, then S is a perfect solution;
(3) If ¯S is a perfect directed code, then S is a perfect directed code.
Proof: Because an arc (u,v)∈A(Γ) will be mapped by γ to an arc (γ(u),γ(v))∈A(¯Γ), the fact that S is independent, which follows from ¯S being independent. Take an element v∈V(Γ)∖S and set ¯v=γ(v), then ¯v∈V(¯Γ)∖¯S.
(1) If ¯S is a perfect kernel, then there exists exactly one ¯s∈¯S such that (¯v,¯s)∈A(¯Γ). Since γ is a covering map, there exists a s∈γ−1(¯s)⊆S such that (v,s)∈A(Γ). Now we show that this element s is unique from the definition of the covering. Suppose s′∈S is an element satisfying (v,s′)∈A(Γ), then (¯v,γ(s′))∈A(¯Γ). So, γ(s)=¯s=γ(s′), and there will be two parallel arcs from ¯v to ¯s if s≠s′, which contradicts to the assumption of ¯Γ being simple. Consequently, S is a perfect kernel of Γ.
(2) can be proved similarly, and (3) follows directly from (1) and (2).
Theorem 2.3. A digraph Γ covers the complete digraph DKn if and only if Γ has a vertex partition S1,S2,…,Sn such that Si,1≤i≤n, are perfect directed codes of Γ.
Proof: The sufficiency follows from Lemma 2.1. For the necessity, let γ:Γ→DKn be a covering map, and let V(DKn)={1,2,…,n}. Set Si=γ−1(i). Clearly, the n-subsets S1,S2,…,Sn form a vertex partition of Γ. Note that {i} is a perfect directed code of DKn for each 1≤i≤n, so Si is a perfect directed code of Γ according to Lemma 2.2.
Example 2.4. Let Γ be the digraph (left) in Figure 1. Set S1={1,2},S2={3,4} and S3={5,6}. Then Si is a perfect directed code of Γ for each i∈{1,2,3}. Moreover, Γ is a cover of the complete digraph DK3 (right).
In this section, we characterize perfect directed codes in Cayley digraphs. For any two subsets U,V of G, set UV={uv | u∈U,v∈V}. If U=∅ or V=∅, then set UV=∅. In particular, if U={u}, then we denote UV by uV; if V={v}, then we denote UV by Uv, .
Lemma 3.1. Let Cay(G,X) be a Cayley digraph of a group G for some X={x1,x2,…,xn} with 1G∉X, and let S be a subset of G. Suppose that g∈G.
(1) The following are equivalent:
(a) S is a perfect solution;
(b) Sg is a perfect solution;
(c) The |X|+1 subsets, xS,x∈X∪{1G}, form a partition of G.
(2) The following are equivalent:
(i) S is a perfect kernel;
(ii) Sg is a perfect kernel;
(iii) The |X|+1 subsets, x−1S,x∈X∪{1G}, form a partition of G.
(3) S is a perfect directed code of Cay(G,X) if and only if S is a perfect directed code of Cay(G,X−1).
Proof: If S is a perfect solution (a perfect kernel), then φ(S) is obviously a perfect solution (a perfect kernel) for each automorphism φ of Cay(G,X). Recall that Rg is an automorphism of Γ for each g∈G, so Rg(S)=Sg is a perfect solution (a perfect kernel) under the condition of S being a perfect solution (a perfect kernel). Similarly, Rg−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∪x1S∪⋯∪xnS. Since S is an independent subset, S∩xiS=∅ for each 1≤i≤n. If xiS∩xjS≠∅ for xi and xj, then xis=xjs′ for some vertices s and s′ in S. This implies that there are two arcs with tails s and s′ that have the same head. Therefore, s=s′ because S is a solution. As a result, xi=xj and the |X|+1 subsets, xS,x∈X∪{1G}, form a partition of G.
For the other direction, assume that the |X|+1 subsets, xS,x∈X∪{1G}, form a partition of G. As xS∩S=∅ for every x∈X, S is an independent subset. Furthermore, for every y∈G∖S, there exists a unique x∈X such that y∈xS. That is to say, there is a unique s∈S such that (s,y)∈A(Γ). So, S is a perfect solution.
(2) Note that if S is a perfect kernel, then G=S∪x−11S∪⋯∪x−1nS. The equivalence of S being a perfect kernel and the partition of G by the |X|+1 subsets, x−1S,x∈X∪{1G}, can be shown in a quite similar way. It is clear that (3) can be inferred directly from (1) and (2).
Remark 3.2. 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 D6={a,b | a3=b2=1,b−1ab=a−1} be the dihedral group of order 6. Take X=S1={a,b},S2={a,ba2}. Then, S1 is a perfect solution but not a perfect kernel of Γ=Cay(D6,X), while S2 is a perfect kernel of Γ but not a perfect solution. In fact, it is easy to see in Figure 2 that Γ does not have perfect directed codes.
Let G be a group and S be a subset of G. If Sg=gS for every g∈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∈X when X generates G.
Corollary 3.4. Let Γ=Cay(G,X) be a Cayley digraph of a group G, and let S be a perfect directed code of Γ. If S is a normal subset of G, then there exists a covering map γ:Γ→DK|X|+1 such that {Sx|x∈X∪{1G}} are the fibres of vertices in DK|X|+1.
Proof: According to Lemma 3.1, the |X|+1 subsets, S,xS=Sx,x∈X, are mutually disjoint perfect directed codes. So, according to Theorem 2.3, Γ covers DK|X|+1 with Sx,x∈X∪{1G}, as the fibres of vertices in DK|X|+1.
Theorem 3.5. Let G be a finite group, Γ=Cay(G,X) be a Cayley digraph with X={x1,x2,…,xn}, and S be a normal subset of G. The following items are equivalent.
(1) S is a perfect directed code of Γ;
(2) There exists a covering map γ:Γ→DKn+1 such that γ−1(v)=S for some v∈V(DKn+1);
(3) |S|=|G|n+1 and S(X∪((X−1X)∖{1G}))∩S=∅;
(4) The n+1 subsets, Sx,x∈X∪{1G}, form a partition of V(Γ).
Proof: Because S is a normal subset of G, Sg=gS for every g∈G, and the fact that (1) and (2) are equivalent is obvious according to Theorem 2.3 and Corollary 3.4.
(1)⇒(3) By Lemma 3.1, the subsets xS,x∈X∪{1G}, form a vertex partition of Γ. So, |S|=|G|n+1 and Sxi∩S=∅ for each xi∈X.
Suppose S(X−1X∖{1G})∩S≠∅, then there exist s1,s2∈S, x1,x2∈X and x1≠x2 such that x−12x1s1=s2, i.e., x1s1=x2s2. This contradicts x1S∩x2S=∅.
(3)⇒(4) Since (X∪X−1X∖{1G})S∩S=∅, for each xi∈X, xiS∩S=∅, i.e., Sxi∩S=∅, and for any two different elements xi,xj∈X, x−1ixjS∩S=∅, i.e., xjS∩xiS=∅, that is Sxj∩Sxi=∅. Furthermore, the condition |S|=|G|n+1 implies G=S∪Sx1∪⋯∪Sxn.
(4)⇒(1) Since the |X|+1 subsets, xS,x∈X∪{1G}, form a vertex partition of Γ, S is a perfect solution according to Lemma 3.1.
For any two different elements xi and xj in X, xiS∩xjS=∅ is equivalent to x−1jxiS∩S=∅, which is Sx−1jxi∩S=∅, and so Sx−1j∩Sx−1i=∅. Hence, Sx−1=x−1S,x∈X∪{1G}, also form a vertex partition of Γ. So, S is a perfect kernel of Γ.
Example 3.6. Let G=Znp be the n-times direct product group of Zp, where p is an odd prime number. Let X={e1,e2,…,en}, where ei=(0,…,1,…,0)∈G has exactly a '1' at the i-th coordinate. Then, Cay(G,X) has a perfect directed code if and only if n=pm−1 for some positive integer m.
Proof: Clearly, 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 Cay(G,X) has a perfect directed code H, then the subsets, H,H+e1,⋯,H+en, form a partition of G. So, pn=|G|=|H|(n+1), and n=pm−1 for some positive integer m.
On the other side, assume n=pm−1 for some positive integer m. Denote the vector space of dimension m on the finite field Fp with p elements as Fmp. Construct an n×m-matrix A: the rows of A are all non-zero vectors in Fmp. Because the rank of A is m, all solutions of ζA=0 where ζ is a vector constitute a (n−m)-dimension subspace T of Fnp.
We claim that T is a perfect directed code of Cay(G,X).
Now we show that T is an independent subset. Otherwise, there exist two different vectors α and β in T such that ei=α−β∈X for some 1≤i≤n. It follows that eiA=0. Note that 0=eiA 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 Fnp. For each δ∈G∖T, suppose there are two different vectors α and β in T such that δ=α+ei=β+ej for 1≤i≠j≤n, then (ei−ej)A=0, which implies that A has two equal rows, also a contradiction. Similarly, there is at most one vector η in T satisfying δ+ek=η for some 1≤k≤n. Considering |T|(n+1)=pn, both T,T+e1,…,T+en and T,T−e1,…,T−en are partitions of G. By Theorem 3.4, T is a perfect directed code.
Remark 3.7. For p=2 in Example 3.6, Cay(G,X) is the hypercube Qn. Moreover, Qn has a Hamming code (or perfect directed code) if and only if n=2m−1 for a positive integer m, see [13].
Let G be a finite group and Cay(G,X) be a Cayley digraph of degree n, which admits a perfect directed code C. Assume X={x1,…,xn}. Then, according to Lemma 3.1, both the n+1 subsets, C,xrC,1≤r≤n, and C,x−1sC,1≤s≤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=|G||H| disjoint subsets Hvi,1≤i≤m, by the equivalent relation of two elements x and y in G being equivalent if and only if xy−1∈H. In group theory, Hvi is called a right coset of H in G, vi∈G a representative element of this coset, and {v1,v2,…,vm} a right transversal of H in G. Similarly, G can also be partitioned into m subsets, uiH,1≤i≤m, by the equivalent relation of two elements x and y in G being equivalent if and only if y−1x∈H. And, uiH is called a left coset of H in G, ui∈G is a representative element of this coset; and {u1,u2,…,um} 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∈G. So, one does not need to distinguish between the left and right cosets of normal subgroups.
Corollary 4.1. Let Γ=Cay(G,X) be a digraph with X={x1,x2,…,xn}, and let H be a normal subgroup of G. The following items are equivalent.
(1) H is a perfect directed code of Γ;
(2) There exists a covering map γ:Γ→DKn+1 such that γ−1(v)=H for some v∈V(DKn+1);
(3) |H|=|G|n+1 and (X∪X−1X)∩H={1G};
(4) X∪{1G} is a transversal of H in G.
Proof: Firstly, we want to show that the condition H(X∪X−1X∖{1G})∩H=∅ is equivalent to that of (X∪X−1X)∩H={1G}.
Assume H(X∪X−1X∖{1G})∩H=∅, then (X∪X−1X∖{1G})∩H=∅ and so (X∪X−1X)∩H={1G}.
If H(X∪X−1X∖{1G})∩H≠∅, then there exist h1,h2,h3,h4∈H, x1,x2,x3∈X, x1≠x2, such that h1=h2x−11x2 or h3x3=h4. Then, 1G≠x−11x2=h−12h1∈H or x3=h−13h4∈H. Therefore, (X∪X−1X)∩H≠{1G}.
Secondly, it is obvious that the subsets, Hx,x∈X∪{1G}, form a vertex partition of Γ if and only if X∪{1G} 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 Ty1,Ty2,⋯,Tym may not be a partition of G even if y1T,y2T,⋯,ymT 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 Γ=Cay(G,X) be a digraph of a group G with X={x1,x2,…,xn}, and let T be a subgroup of G. The following items are equivalent.
(1) T is a perfect directed code of Γ;
(2) There exists a covering map γ:Γ→DKn+1 such that γ−1(v)=T for some v∈V(DKn+1);
(3) |T|=|G|n+1, (X∪X−1X∪XX−1)∩T={1G};
(4) X∪{1G} is a transversal of T.
Proof: Under the condition of T being a perfect directed code, the n+1 subsets, T,x1T,…,xnT, form a partition of G according to Lemma 3.1. So, T has n+1 left or right cosets in G, X∪{1G} is a left transversal of T, and |G|=|T|(n+1). Because Tg is a perfect directed code of Γ for every g∈G, the n+1 right cosets of T are mutually disjoint perfect directed codes of Γ. According to Theorem 2.3, (1) and (2) are equivalent.
(1)⇒(3): Take an element a∈(X∪X−1X∪XX−1)∩T, then a∈X∩T or a=x−1ixj∈T or a=xrx−1t∈T for xi,xj,xr,xt in X. Under the assumption of T being a perfect directed code, for any x,xi,xj∈X and xi≠xj,
T∩xT=xiT∩xjT=T∩x−1T=x−1iT∩x−1jT=∅, |
so a=1G.
(3)⇒(4): The assumption of (X∪X−1X∪XX−1)∩T={1G} implies that T∩xiT=xiT∩xjT=T∩x−1iT=x−1iT∩x−1jT=∅ for any two different elements xi and xj in X. Furthermore, because |T|=|G|n+1, both X∪{1G} and X−1∪{1G} are left transversals of T.
By taking the inverse subset of x−1T for every x∈X, T∩Txi=Txi∩Txj=∅, which follows directly from T∩x−1iT=x−1iT∩x−1jT=∅ for any two different elements xi and xj in X. Therefore, X∪{1G} is also a right transversal of T.
(4)⇒(1): The assumption of X∪{1G} being both a left and a right transversal of T in G implies that both T,x1T,…,xnT and T,Tx1,…,Txn are partitions of G. Therefore, T,x−11T,…,x−1nT form a partition of G as well. According to Lemma 3.1, T is a perfect directed code of Γ.
Remark 4.3. In Theorem 4.2, if X=X−1, then clearly X∪{1G} 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 D6 can be a perfect directed code.
Example 4.4. Let p be an odd prime number and k≥2 be a factor of p−1. Let G=⟨a,b | ap=bk=1G,b−1ab=ai,ik≡1 mod p⟩ be a split metacyclic group, which is a group of order pk. Take T=⟨b⟩ and T is not normal in G. Set X={aib | 1≤i≤p−1}. Then, X∪{1G} is both a left and a right transversal of T. So, T is a perfect directed code of 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=⟨a⟩ be a cyclic group of order n. Then, a connected Cayley digraph Cay(G,X) of degree m−1 admits a perfect directed code if m divides n and xix−1j∉⟨am⟩ for any two distinct xi and xj in X∪{1G}.
Proof: Assume that m|n and xix−1j∉⟨am⟩ for any two distinct xi and xj in X∪{1G}. Set T=⟨am⟩. Then, under the condition of xix−1j∉T, both the |X|+1 subsets, T,xiT,xi∈X, and T,x−1jT,xj∈X, form partitions of G. So, according to Lemma 3.1, T is a perfect directed code of Cay(G,X).
Note that the condition xix−1j∉⟨am⟩ in Lemma 4.5 is not necessary, which is different from that in Cayley graphs [7].
Example 4.6. Let G=⟨a⟩ be the cyclic group of order 24. Set C={1G,a2,a8,a10,a16,a18} and X={a,a4,a5}. It is easy to check that both the 4 subsets, C,aC,a4C,a5C and C,a−1C,a−4C,a−5C form partitions of G. So, C is a perfect directed code of Cay(G,X).
A subgroup T of G is called a perfect directed coding subgroup if there exists X⊂G such that T is a perfect directed code of the Cayley digraph Cay(G,X), and T is called a connected perfect directed coding subgroup if 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 Φ(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∖{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 Γ be an undirected graph, S⊆V(Γ), and N(S) be a set of vertices of V(Γ) 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 Γ with vertex sets V1 and V2 contains a complete matching from V1 to V2 iff
|N(S)|≥|S|foreveryS⊆V1. |
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={x1,x2,…,xn−1}⊆G such that X∪{1G} is a transversal of T in G.
Proof Let {a1,a2,…,an−1}∪{1G} be a left transversal of T and {b1,b2,…,bn−1}∪{1G} be a right transversal of T. Let Γ be a bipartite graph with vertex sets V1={aiT|1≤i≤n−1} and V2={Tbi|1≤i≤n−1} such that {aiT,Tbj} is an edge if and only if aiT∩Tbj≠∅. Let S be an arbitrary subset of V1 and S={giT|1≤i≤m} for some m. We claim that there are at least m vertices in N(S). Otherwise, |⋃x∈N(S)x|<|⋃x∈Sx|=m|T|, which implies that there exists a vertex Tb∉N(S) adjacent to a vertex in S, a contradiction. So |N(S)|≥|S|. By Proposition 4.8, Γ contains a complete matching from V1 to V2. So we may assume, without loss of generality, that
{{aiT,Tbi}|1≤i≤n−1} |
is a complete matching. Chose xi∈aiT∩Tbi for 1≤i≤n−1 and let X={x1,x2,…,xn−1}. Then X∪{1G} 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≠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 Cay(G,X) is called a transversal Cayley digraph if X∪{1G} 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={x1,x2,…,xn−1}⊆G such that X∪{1G} is a transversal of H in G. By Theorem 4.2, H is a perfect directed code of the transversal Cayley digraph 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 Φ(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 Cay(G,X). And so G=⟨X,T⟩=⟨X,Φ(G)⟩. From Proposition 4.7, we have G=⟨X⟩. It follows that 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 Φ(G)=G′⟨ap|a∈G⟩ 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=⟨a⟩ and X∪{1G} be a transversal of T. Then we may assume a∈X. And so G=⟨X⟩. Clearly, T is a perfect directed code of the connected Cayley digraph Cay(G,X). Then T is a perfect directed coding subgroup, as desired.
Let G=⟨a,b|an=b2=1,ab=a−1⟩ be a dihedral group. Then ⟨a⟩ is not a perfect directed coding subgroup of any connected Cayley digraph, and ⟨b⟩ 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.
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.
The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.
The authors thank the referees for the helpful comments and suggestions. This work is supported by NSFC (No. 12101535) and NSFS (No. ZR2023MA078, ZR2020MA044).
The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.
[1] |
S. D. Andres, W. Hochstättler, Perfect Digraphs, J. Graph Theory, 79 (2014), 21–29. https://doi.org/10.1002/jgt.21811 doi: 10.1002/jgt.21811
![]() |
[2] |
T. Araki, On the k-tuple domination in de Bruijn and Kautz digraphs, Inform. Process. Lett., 104 (2007), 86–90. https://doi.org/10.1016/j.ipl.2007.05.010 doi: 10.1016/j.ipl.2007.05.010
![]() |
[3] |
T. Araki, The k-tuple twin domination in de Bruijn and Kautz digraphs, Discrete Math., 308 (2008), 6406–6413. https://doi.org/10.1016/j.disc.2007.12.020 doi: 10.1016/j.disc.2007.12.020
![]() |
[4] |
S. Arumugam, K. Ebadi, L. Sathikala, Twin domination and twin irredundance in digraphs, Appl. Anal. Discrete Math., 7 (2013), 275–284. https://doi.org/10.2298/AADM130429007A doi: 10.2298/AADM130429007A
![]() |
[5] | M. Atapour, A. Bodaghli, S. M. Sheikholeslami, Twin signed total domination numbers in directed graphs, Ars Combin., 138 (2018), 119–131. |
[6] | B. Bollobás, Modern graph theory, Springer New York, 1998. |
[7] |
R. Q. Feng, H. Huang, S. M. Zhou, Perfect codes in circulant graphs, Discrete Math., 340 (2017), 1522–1527. https://doi.org/10.1016/j.disc.2017.02.007 doi: 10.1016/j.disc.2017.02.007
![]() |
[8] | J. Bang-Jensen, G. Gutin, Digraphs: theory, algorithms and applications (Second Edition), Springer Science Business Media, 2008. |
[9] | G. Chartrand, P. Dankelmann, M. Schultz, H. C. Swart, Twin domination in digraphs, Ars Combin., 67 (2003), 105–114. |
[10] | J. Ghoshal, R. Laskar, D. Pillone, Topics on domination in directed graphs, Domination in Graphs Advanced Topics, (2017), 401–438. |
[11] |
P. Hall, On representatives of subsets, J. London Math. Soc., 10 (1935), 26–30. https://doi.org/10.1112/jlms/s1-10.37.26 doi: 10.1112/jlms/s1-10.37.26
![]() |
[12] |
J. Huang, J. M. Xu, The total domination and total bondage numbers of extended de Bruijn and Kautz digraphs, Comput. Math. Appl., 53 (2007), 1206–1213. https://doi.org/10.1016/j.camwa.2006.05.020 doi: 10.1016/j.camwa.2006.05.020
![]() |
[13] |
J. Lee, Independent perfect domination sets in Cayley graphs, J. Graph Theory, 37 (2001), 213–219. https://doi.org/10.1002/jgt.1016 doi: 10.1002/jgt.1016
![]() |
[14] |
Y. Kikuchi, Y. Shibata, On the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs, Inform. Process. Lett., 86 (2003), 79–85. https://doi.org/10.1016/S0020-0190(02)00479-9 doi: 10.1016/S0020-0190(02)00479-9
![]() |
[15] | H. E. Rose, A course on finite groups, Springer London, 2009 |
[16] |
E. F. Shan, Y. X. Dong, Y. K. Cheng, The twin domination number in generalized de Bruijn digraphs, Inform. Process. Lett., 109 (2009), 856–860. https://doi.org/10.1016/j.ipl.2009.04.010 doi: 10.1016/j.ipl.2009.04.010
![]() |
[17] |
Y. L. Wang, Efficient twin domination in generalized De Bruijn digraphs, Discrete Math., 338 (2015), 36–40. https://doi.org/10.1016/j.disc.2014.10.014 doi: 10.1016/j.disc.2014.10.014
![]() |
[18] | M. Ždímalová, M. Olejár, Large Cayley digraphs of given degree and diameter from sharply t-transitive groups Australasian J. Combin., 47 (2010), 211–216. |
[19] |
M. Ždímalová, L. Staneková, Which Faber-Moore-Chen digraphs are cayley digraphs? Discrete Math., 310 (2010), 2238–2240. https://doi.org/10.1016/j.disc.2010.04.020 doi: 10.1016/j.disc.2010.04.020
![]() |