Research article Special Issues

Perfect directed codes in Cayley digraphs

  • 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

    Related Papers:

    [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,vS, (u,v)A(Γ). An independent subset S of V(Γ) is called a perfect kernel of Γ if for each vV(Γ)S there exists a unique element xS such that (v,x)A(Γ), while S is called a perfect solution of Γ if for each wV(Γ)S there exists a unique element yS 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 1GX 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 gG and xX. If X=X1, 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 gG and define Rg:GG as Rg(u)=ug for each element uG. 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 xV(Γ), 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 S1S2 is called a dimatching if for every vertex u1S1 there is exactly one vertex v2S2 and one vertex w2S2 (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 1in.

    Proof: (1) Let S1 and S2 be two perfect directed codes of a digraph Γ, and let S=S1S2. Let |S1|=1. Assume that |S2|2. Let uS1 and v,wS2, vw. 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 (S1S2)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 | 1in} 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, ¯SV(¯Γ) 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 vV(Γ)S and set ¯v=γ(v), then ¯vV(¯Γ)¯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 sS 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 ss, 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,1in, 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 1in, 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).

    Figure 1.  Digraph Γ (left) covers DK3 (right).

    In this section, we characterize perfect directed codes in Cayley digraphs. For any two subsets U,V of G, set UV={uv | uU,vV}. 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 1GX, and let S be a subset of G. Suppose that gG.

    (1) The following are equivalent:

    (a) S is a perfect solution;

    (b) Sg is a perfect solution;

    (c) The |X|+1 subsets, xS,xX{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, x1S,xX{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,X1).

    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 gG, so Rg(S)=Sg is a perfect solution (a perfect kernel) under the condition of S being a perfect solution (a perfect kernel). Similarly, Rg1(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=Sx1SxnS. Since S is an independent subset, SxiS= for each 1in. If xiSxjS 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,xX{1G}, form a partition of G.

    For the other direction, assume that the |X|+1 subsets, xS,xX{1G}, form a partition of G. As xSS= for every xX, S is an independent subset. Furthermore, for every yGS, there exists a unique xX such that yxS. That is to say, there is a unique sS such that (s,y)A(Γ). So, S is a perfect solution.

    (2) Note that if S is a perfect kernel, then G=Sx11Sx1nS. The equivalence of S being a perfect kernel and the partition of G by the |X|+1 subsets, x1S,xX{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,b1ab=a1} 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.

    Figure 2.  A perfect solution {a,b} and a perfect kernel {a,ba2}.

    Let G be a group and S be a subset of G. If Sg=gS for every gG, then S is called a normal subset of G. It is obvious that S is normal if and only if Sx=xS for every xX 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|xX{1G}} are the fibres of vertices in DK|X|+1.

    Proof: According to Lemma 3.1, the |X|+1 subsets, S,xS=Sx,xX, are mutually disjoint perfect directed codes. So, according to Theorem 2.3, Γ covers DK|X|+1 with Sx,xX{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 vV(DKn+1);

    (3) |S|=|G|n+1 and S(X((X1X){1G}))S=;

    (4) The n+1 subsets, Sx,xX{1G}, form a partition of V(Γ).

    Proof: Because S is a normal subset of G, Sg=gS for every gG, 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,xX{1G}, form a vertex partition of Γ. So, |S|=|G|n+1 and SxiS= for each xiX.

    Suppose S(X1X{1G})S, then there exist s1,s2S, x1,x2X and x1x2 such that x12x1s1=s2, i.e., x1s1=x2s2. This contradicts x1Sx2S=.

    (3)(4) Since (XX1X{1G})SS=, for each xiX, xiSS=, i.e., SxiS=, and for any two different elements xi,xjX, x1ixjSS=, i.e., xjSxiS=, that is SxjSxi=. Furthermore, the condition |S|=|G|n+1 implies G=SSx1Sxn.

    (4)(1) Since the |X|+1 subsets, xS,xX{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, xiSxjS= is equivalent to x1jxiSS=, which is Sx1jxiS=, and so Sx1jSx1i=. Hence, Sx1=x1S,xX{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=pm1 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=pm1 for some positive integer m.

    On the other side, assume n=pm1 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 (nm)-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 1in. 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 δGT, suppose there are two different vectors α and β in T such that δ=α+ei=β+ej for 1ijn, then (eiej)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 1kn. Considering |T|(n+1)=pn, both T,T+e1,,T+en and T,Te1,,Ten 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=2m1 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,1rn, and C,x1sC,1sn, 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,1im, by the equivalent relation of two elements x and y in G being equivalent if and only if xy1H. In group theory, Hvi is called a right coset of H in G, viG 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,1im, by the equivalent relation of two elements x and y in G being equivalent if and only if y1xH. And, uiH is called a left coset of H in G, uiG 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 yG. 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 vV(DKn+1);

    (3) |H|=|G|n+1 and (XX1X)H={1G};

    (4) X{1G} is a transversal of H in G.

    Proof: Firstly, we want to show that the condition H(XX1X{1G})H= is equivalent to that of (XX1X)H={1G}.

    Assume H(XX1X{1G})H=, then (XX1X{1G})H= and so (XX1X)H={1G}.

    If H(XX1X{1G})H, then there exist h1,h2,h3,h4H, x1,x2,x3X, x1x2, such that h1=h2x11x2 or h3x3=h4. Then, 1Gx11x2=h12h1H or x3=h13h4H. Therefore, (XX1X)H{1G}.

    Secondly, it is obvious that the subsets, Hx,xX{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 vV(DKn+1);

    (3) |T|=|G|n+1, (XX1XXX1)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 gG, 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(XX1XXX1)T, then aXT or a=x1ixjT or a=xrx1tT for xi,xj,xr,xt in X. Under the assumption of T being a perfect directed code, for any x,xi,xjX and xixj,

    TxT=xiTxjT=Tx1T=x1iTx1jT=,

    so a=1G.

    (3)(4): The assumption of (XX1XXX1)T={1G} implies that TxiT=xiTxjT=Tx1iT=x1iTx1jT= for any two different elements xi and xj in X. Furthermore, because |T|=|G|n+1, both X{1G} and X1{1G} are left transversals of T.

    By taking the inverse subset of x1T for every xX, TTxi=TxiTxj=, which follows directly from Tx1iT=x1iTx1jT= 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,x11T,,x1nT 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=X1, 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 k2 be a factor of p1. Let G=a,b | ap=bk=1G,b1ab=ai,ik1 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 | 1ip1}. 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 m1 admits a perfect directed code if m divides n and xix1jam for any two distinct xi and xj in X{1G}.

    Proof: Assume that m|n and xix1jam for any two distinct xi and xj in X{1G}. Set T=am. Then, under the condition of xix1jT, both the |X|+1 subsets, T,xiT,xiX, and T,x1jT,xjX, form partitions of G. So, according to Lemma 3.1, T is a perfect directed code of Cay(G,X).

    Note that the condition xix1jam 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,a1C,a4C,a5C 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 XG 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, SV(Γ), 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|foreverySV1.

    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,,xn1}G such that X{1G} is a transversal of T in G.

    Proof Let {a1,a2,,an1}{1G} be a left transversal of T and {b1,b2,,bn1}{1G} be a right transversal of T. Let Γ be a bipartite graph with vertex sets V1={aiT|1in1} and V2={Tbi|1in1} such that {aiT,Tbj} is an edge if and only if aiTTbj. Let S be an arbitrary subset of V1 and S={giT|1im} for some m. We claim that there are at least m vertices in N(S). Otherwise, |xN(S)x|<|xSx|=m|T|, which implies that there exists a vertex TbN(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}|1in1}

    is a complete matching. Chose xiaiTTbi for 1in1 and let X={x1,x2,,xn1}. 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 HG. 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,,xn1}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)=Gap|aG 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 aX. 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=a1 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
  • Reader Comments
  • © 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(954) PDF downloads(55) Cited by(0)

Figures and Tables

Figures(2)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog