°c 1998 Kluwer Academic Publishers. Manufactured in The Netherlands.
On Cayley Graphs of Abelian Groups
CAI HENG LI [email protected]
Department of Mathematics, University of Western Australia, Nedlands, W.A. 6907, Australia Received March 9, 1995; Revised April 18, 1997
Abstract. Let G be a finite Abelian group and Cay(G,S)the Cayley (di)-graph of G with respect to S, and let A=Aut Cay(G,S)and A1the stabilizer of 1 in A. In this paper, we first prove that if A1is unfaithful on S then S contains a coset of some nontrivial subgroup of G, and then characterize Cay(G,S)if A1Scontains the alternating group on S. Finally, we precisely determine all m-DCI p-groups for 2≤m≤p+1, where p is a prime.
Keywords: Cayley graph, isomorphism, CI-subset, m-DCI group
1. Introduction
Let G be a finite group and S a Cayley subset of G, that is, S does not contain the identity of G. The Cayley(di)-graph Cay(G,S)of G with respect to S has the elements of G as vertices and the pairs(g,sg),g ∈ G,s ∈ S, as edges. Given a Cayley subset S of G, if, for any Cayley subset T of G, Cay(G,S)∼=Cay(G,T)implies T =Sσ for some σ ∈ Aut(G), then S is called a CI-subset (CI stands for Cayley Isomorphism). A finite group G is called an m-DCI group if all of its Cayley subsets of G of size at most m are CI-subsets; G is called a DCI-group if it is a|G|-DCI group. Similarly, G is called an m-CI group if all Cayley subsets S of G of size at most m with S=S−1are CI-subsets, G is called a CI-group if G is an|G|-CI group. The problem of determining which groups are m-DCI groups and m-CI groups has been investigated for a long time, see [6, 10, 12]
for references. Recently, all m-DCI groups and all m-CI groups for m ≥ 2 have been classified in [10] and [9], respectively, in the sense that all the possibilities for such groups are explicitly listed. However, it is still a difficult question to determine which of them are really m-DCI (m-CI) groups. Babai and Frankl [2] asked whether the elementary abelian group Zdp for any p and d was an m-CI group for all m ≤ |G|(in other words, Zdp is a CI-group). Godsil [6] and Dobson [4] proved this to be true for d = 2,3, respectively.
However, recently Nowitz [11] gave a negative answer to the question by proving that Z26 is not a 31-CI group. It is not known if this the answer of the question is positive for odd prime p and d ≥ 4. The main aims of this paper are to characterize Cayley graphs Cay(G,S)of abelian groups by the action of A1on S, where A1 is the stabilizer of 1 in Aut Cay(G,S), and to determine precisely m-DCI p-groups for 2 ≤m ≤ p+1, which implies that the answer of Babai and Frankl’s question is positive for any p,d and m≤ p+1.
Notation In this paper, Zn denotes a cyclic group of order n, Q8 is the quaternion group of order 8. Recall that a group is called homocylic if it is a direct product of some cyclic
groups of the same order. For groups G and H , H ≤ G denotes that H is a subgroup of G, and GoH denotes a semidirect product of G by H . For a positive integer n, Cn
denotes the directed cycle of length n, Kn denotes the complete graph on n vertices and Kn,ndenotes the complete-bipartite graph on 2n vertices. For a directed graph0=(V,E), its complement0¯ =(V,E¯)is the directed graph with vertex set V such that(a,b)∈ ¯E if and only if(a,b)6∈ E . The direct product01×02of two directed graphs01=(V1,E1) and02=(V2,E2)is the directed graph with vertex set V1×V2such that((a1,a2), (b1,b2)) is an edge if and only if either(a1,b1)∈ E1 and a2 =b2, or(a2,b2)∈ E2and a1 =b1. The lexicographic product01[02] of two directed graphs01=(V1,E1)and02=(V2,E2) is the graph with vertex set V1×V2such that((a1,a2), (b1,b2))is an edge if and only if either(a1,b1)∈ E1or a1 =b1 and(a2,b2)∈ E2. For any vertex x of graph Cay(G,S), the neighborhood0(x)of x in Cay(G,S)equals x S = {xai |1 ≤i ≤m}. Let0i(x)= {y∈G|d(x,y)=i}, where d(x,y)denotes the distance from x to y in Cay(G,S). Note that0(x)=01(x).
In Section 2, we quote some results which are used in the following sections. Section 3 characterizes some Cayley graphs on Abelian groups, and Section 4 precisely determines m-DCI p-groups for certain values of m.
2. Preliminaries
In this section, we quote some results which we need in the following sections. Let G be a finite group, S a Cayley subset of G and let A=Aut Cay(G,S). Babai [1] gave a criterion for a subset of G to be a CI-subset.
Theorem 2.1 ([1]) For a given group G and a Cayley subset S of G,S is a CI-subset if and only if for anyτ∈Sym(G)withτGτ−1≤ A,there existsα∈ A such thatαGα−1= τGτ−1,where Sym(G)is the symmetric group on G.
The normalizer of G in A is often useful for characterizing Cay(G,S).
Lemma 2.2 ([5]) Let A=Aut Cay(G,S)and Aut(G,S)= {α∈Aut(G)|Sα =S}. Then NA(G)equals a semidirect product of G by Aut(G,S),that is,NA(G)=GoAut(G,S).
All finite m-DCI groups for m ≥2 have been explicitly listed in [10], in particular, we have
Lemma 2.3 ([10, Proposition 3.1]) Let G be a finite m-DCI p-group,where m≥2 and p is a prime.
(1) If p is odd and 2≤m≤ p−1,then G is homocyclic.
(2) If m=p,then either G is elementary Abelian,cyclic,or G =Q8. (3) If m=p+1,then either G is elementary Abelian,or G=Z4or Q8. Lemma 2.4 ([16]) The quaternion group Q8is a DCI-group.
3. Cayley graphs of Abelian groups
In this section, we characterize some properties of Cayley graphs of Abelian groups. Let G be a finite group, S = {a1,a2, . . . ,am}be a Cayley subset of G and0 =Cay(G,S). Let A be the full automorphism group of0and A1the stabilizer of 1 in A. For h distinct elements ai1,ai2, . . . ,aih∈ S and y∈G, let
(0¡
yai1, . . . ,yaih¢
= 0¡ yai1¢
∩ · · · ∩ 0¡ yaih¢
, 0∗¡
yai1, . . . ,yaih
¢ = 0¡
yai1, . . . ,yaih
¢² S
x∈R0(yx),
where R=S\{ai1, . . . ,aih}, that is,0∗(yai1, . . . ,yaih)is the set of all vertices of0which are joined to every element of{yai1, . . . ,yaih}and to no element of y R. Let
0i∗=max{|0∗(u1, . . . ,ui)| |u1, . . . ,ui ∈S}.
If R= {u1, . . . ,ui)⊆S, then denote0∗(u1, . . . ,ui)by0∗(R)sometimes.
Lemma 3.1 Suppose that G is an Abelian group. Then
(i) 1∈0∗(W)for W ⊆S if and only if W =W−1and(S\W)∩(S\W)−1 = ∅;
(ii) 0∗(x x1, . . . ,x xk)=x0∗(x1, . . . ,xk)for any x∈G and any x1, . . . ,xk∈ S; (iii) 0k∗≤k for every k≥1;
(iv) every element of02(1)lies in0∗(x1, . . . ,xk)for some x1, . . . ,xk∈ S.
Proof: By the definition of0∗(x1, . . . ,xk), part (i) is clear. Again by definition, we have y∈0∗(x x1, . . . ,x xk) ⇔ y∈0∗(x x1)∩ · · · ∩0∗(x xk)²[
z∈R
0(x z)
⇔ x−1y∈0(x1)∩ · · · ∩0(xk)²[
z∈R
0(z)
⇔ y∈x¡
0(x1)∩ · · · ∩0(xk)²[
z∈R
0(z)¢
=x0∗(x1, . . . ,xk),
where R=S\{x1, . . . ,xk}. Thus part (ii) is true. Now suppose that0∗k= |0∗(x1, . . . ,xk)|
for some x1, . . . ,xk∈ S. By definition, x1x6∈0∗(x1, . . . ,xk)for any x ∈S\{x1, . . . ,xk), so 0∗(x1, . . . ,xk) ⊆ {x1x1, . . . ,x1xk}. Hence 0k∗ = |0∗(x1, . . . ,xk)| ≤ k as in (iii).
Finally, for any y∈02(1), let{x1, . . . ,xk} = {x∈S |y∈0(x)}. Then y∈0∗(x1, . . . ,xk)
is as in (iv). 2
It is clear that if Cay(G,S)∼=Cl[K¯m] for m>1 then A1is not faithful on S. Conversely, the following theorem shows that if A1is not faithful on S then Cay(G,S)contains such a subgraph.
Theorem 3.2 Let G be an Abelian group and0=Cay(G,S)for some S⊂G such that G = hSi. Let A=Aut0and A1 the stabilizer of 1 in A. Then either A1is faithful on S, or S contains a coset of some nontrivial subgroup of G and0has a subgraph isomorphic to Cl[K¯n] for some integers l and n.
Proof: Let S = {a1,a2, . . . ,am}. Assume first that for any integer h ≥ 1 and any h elements x1, . . . ,xh ∈ S, |0∗(x1, . . . ,xh)| ≤ 1. We claim that A1 is faithful on S. For any y ∈02(1),let{ai1, . . . ,aih} = {x ∈ S | y ∈0(x)}. Then y is the unique element of 0∗(ai1, . . . ,aih). Ifα∈ A1such that xα=x for all x ∈ S, thenαfixes ai1, . . . ,aih. Thus αfixes0∗(ai1, . . . ,aih), and soαfixes y. Hence xα =x for all x∈02(1). SincehSi =G, Cay(G,S)is connected, and it follows that xα =x for all x∈ V0. Henceα=1 and A1
is faithful on S.
Assume now that there are some h vertices ai1, . . . ,aihsuch that|0∗(ai1, . . . ,aih)| ≥2.
Letw,y∈0∗(ai1, . . . ,aih). Without loss of generality, we may assume that{i1, . . . ,ih} = {1, . . . ,h}. By the definition of 0∗(a1, . . . ,ah), there exist u1, . . . ,uh, v1, . . . , vh ∈ {a1, . . . ,ah}such that
(a1u1=a2u2= · · · =ahuh =w,
a1v1=a2v2 = · · · =ahvh =y,
where ui6=vi and{u1, . . . ,uh} = {v1, . . . , vh} = {a1, . . . ,ah}. Since {u1, . . . ,uh} = {v1, . . . , vh}, there exist i1 6= 1, i2 6= i1, . . . ,ik 6= ik−1 for some k ≤ h such that v1=ui1, vi1=ui2, . . . , vik−1=uik andvik=u1. Thus
(a1u1=ai1ui1 = · · · =aikuik,
a1ui1 =ai1ui2 = · · · =aiku1.
For convenience, without loss of generality, we may assume that i1=2, i2 =3, . . . ,ik= k+1. Then we have
(a1u1=a2u2= · · · =ak+1uk+1, a1u2=a2u3= · · · =ak+1u1.
Thus a1u1aiui+1 = a1u2aiui for i ≤ k and a1u1ak+1u1 = a1u2ak+1uk+1. Therefore, u1ui+1 =u2ui for i ≤ k and u21 =u2uk+1. Let U = {u1, . . . ,uk+1}. Then u1U=u2U . Similarly, we have u1U= · · · =uk+1U . We claim that a1−1U is a subgroup of G. In fact, for any i,j with 1≤i,j ≤k+1, there exists an integer l such that u1ui=ujul because u1U =ujU . Thus uiu−j1=u−11ul and so
u−11ui·¡ u−11uj
¢−1
=uiu−j1 =u−11ul∈u−11U.
Therefore, u−11U is a subgroup of G and U is a coset of the subgroup u−11U . Now Cay(hUi,U)∼=Cl[K¯|U|] is a subgraph of Cay(G,S)as in the theorem. This completes the
proof of the theorem. 2
Next we are going to characterize Cayley graphs Cay(G,S)for which A1S is the alter- nating group or the symmetric group of degree|S|. To do this, we first prove the following lemma.
Lemma 3.3 Let G be an Abelian group,and let S,T be two Cayley subsets of G such that G = hSi and Cay(G,S) ∼= Cay(G,T). If0∗(x,y) = {x y}for all x,y ∈ S and 0∗(u, v)= {uv}for all u, v∈T,then every isomorphism preserving 1 between Cay(G,S) and Cay(G,T)induces an automorphism of G.
Proof: Let S = {a1,a2, . . . ,am}and T = {b1,b2, . . . ,bm}. Without loss of generality, assume thatρis an isomorphism from Cay(G,S)to Cay(G,T)such that 1→1, ai →bi
for i =1,2, . . . ,m. Then for any i6= j ,
ρ:{aiaj} =0∗(ai,aj)7→0∗(bi,bj)= {bibj}.
We claim thatρis an automorphism of G. To prove this, we need only verify that for all integers n1,n2, . . . ,nm≥0,
¡a1n1a2n2· · ·amnm¢ρ
=bn11bn22· · ·bnmm, (1) by induction on n1+n2+ · · · +nm. Since
ρ:
½ai →bi, for 1≤i ≤m, aiaj →bibj, for i 6= j, we haveρ:
©ai2ª
=0(ai)\{aiaj| j 6=i} 7→0(bi)\{bibj | j6=i} =© b2iª
for all i =1,2, . . . ,m. In other words, (1) holds for n1+n2+ · · · +nm≤2. Now assume inductively that the equality (1) holds for n1+n2+ · · · +nm≤N , where N ≥2. Let
a= Ym
j=1
an
0j
j , where Xm
j=1
n0j =N−1.
By the induction assumption, we have
ρ: (
a→b=Qm j=1bn
0j
j ,
aai→bbi, for 1≤i ≤m.
Since G is Abelian, for any x ∈ hSi, y ∈ hTiand any i 6= j , we have 0∗(xai,xaj)= {xaiaj}and0∗(ybi,ybj)= {ybibj}. Henceρ:
({aaiaj} =0∗(aai,aaj)7→0∗(bbi,bbj)= {bbibj}, for 1≤i 6= j ≤m,
©aai2ª
=0(aai)\{aaiaj| j 6=i} 7→0(bbi)\{bbibj| j 6=i} =© bb2iª
.
Therefore, the equality (1) holds for n1+n2+ · · · +nm = N +1. By induction, the equality (1) holds for all n1,n2, . . . ,nm≥0. Henceρis an automorphism of G sending S
to T . 2
To prove our next theorem, we need some notation. If a,b ∈ S and b6=a−1, then the product ab (in G) is said to be a word of length 2 on S. Letw(ab)be the number of all words of length 2 on S which are equal to ab, that is,w(ab)= |{uv |uv =ab and u, v∈ S}|. For Y ⊆02(1), letw(Y)be the number of all words of length 2 on S which are equal to an element of Y , that is,w(Y)=P
y∈Yw(y).
Lemma 3.4 Using the notation defined above,we have
(i) if 16=ab∈0∗(u1,u2, . . . ,ui),thenw(ab)=i for any u1,u2, . . . ,ui ∈S; (ii) if|0∗(u1, . . . ,ui)| = j then
w(0∗(u1, . . . ,ui))=
(i j if 16∈0∗(u1, . . . ,ui), i(j−1) if 1∈0∗(u1, . . . ,ui);
(iii) |02(1)| ≤w(02(1))and if 1∈0∗(R)thenw(02(1))=m2− |R|for any R⊆S; (iv) if AS1 ≥Alt(|S|),then 1∈0∗(R)for R⊆S implies R=S.
Proof: By definition, part (i) is clear. It follows that part (ii) holds. Now let S = {a1, . . . ,am}. Then02(1)= {aiaj | 1 ≤i,j ≤ m}\{1}. It follows that part (iii) is true.
Noting that AS1is(m−2)-transitive on S, in particular, transitive and 2-set-transitive on S,
part (iv) is clearly true. 2
Now we can prove our next result.
Theorem 3.5 Let G be an Abelian group,and let S be a generating subset of G of size m. Let0=Cay(G,S),and let A=Aut0and A1the stabilizer of 1 in A. If AS1 ≥Alt(m), the alternating group of degree m,then one of the following holds:
(i) S=G\{1}and0∼=Km+1;
(ii) S=a H for some H≤G,and0∼=Km,mor C|G|/m[K¯m];
(iii) S=b H\{b}for some H≤G, 0∼=C|G|/(m+1)[K¯m+1]−o|G(b|)Co(b); (iv) S=aLfor some a∈ S and some L≤Aut(G,S),and GCA;
(v) either G is cyclic,or G=Zn×B,where n is odd and B is a 2-group of exponent 4, and02(1)=S
u,v∈S0∗(u, v)∪0∗(S)\{1}.
Proof: First assume that m=2 and S= {a,b}. If b=a−1then G = haiis cyclic and0 is a cycle of length n :=o(a). Thus A∼=D2n, and so part (iv) holds in this case. Suppose that b 6=a−1. If|0∗(a,b)| = 1, then a2 6=b2 and so0∗(a,b)= {ab}. It follows from Lemma 3.3 that part (iv) holds. If|0∗(a,b)| = 2 then0∗(a,b)= {ab =ba,a2 =b2}. Thus{1,a−1b}is a subgroup of G of order 2, and S =a{1,a−1b}as in part (ii). Hence 0i(1)= ai{1,a−1b}for all i ≥ 1. Hence|0i(1)| = 2, and it follows that Cay(G,S)∼= C|G|/2[K¯2].
In the following, assume that m≥3 and S= {a1,a2, . . . ,am}. Since AS1 ≥Alt(m), A1S is(m−2)-transitive on S, in particular, A1S is 2-set-transitive on S. By Lemma 3.1(iv),
any element of02(1)belongs to 0∗(R)for some R ⊆ S. Since either0∗(ai) = ∅ or 0∗(ai)= {a2i}and ai2 6=ajak for any j,k 6=i , there is at least one n ∈ {2, . . . ,m}such that0∗n ≥1.
(1) Assume that there exists an integer n with 3≤n≤m−2 such that0∗n =r ≥1. Then there are n vertices c1, . . . ,cn ∈S such that|0∗(c1, . . . ,cn)| =r . Thus0∗(c1, . . . ,cn)con- tains exactly r elements of02(1). By Lemma 3.4(ii) and (iv),w(0∗(c1,c2, . . . ,cn))=r n.
Since A1is(m−2)-transitive on S, for any n elements x1, . . . ,xnof S,w(0∗(x1, . . . ,xn))= r n. Hence
m2≥w(02(1))≥ X
x1,...,xn∈S
w(0∗(x1, . . . ,xn))=r n µm
n
¶ .
However, it is easy to see that r n(mn) >m2since 3≤n ≤m−2, a contradiction. Thus 0∗n =0 for 3≤n≤m−2.
(2) Assume that 02∗ = 0m∗−1 = 0. Then 02(1) = (0∗(S)\{1})∪0∗(a1)∪ · · · ∪ 0∗(am)⊆(0∗(S)\{1})∪ {a12, . . . ,a2m}. Thus aiaj∈0∗(S)for any ai6=aj. Since no two of a1a2, . . . ,a1amare equal,|0∗(S)| ≥m−1≥2. Thus for any i,j 6=1, there are integers h,k such that a1ai =ajah and a1aj =aiak. It follows that a12=ahakand so0∗(a1)= ∅. Thus0∗(S)\{1} =02(1). Hence every vertex in02(1)is joined to all vertices in0(1)=S.
Thus if 1 ∈ 0∗(S)then Cay(G,S) ∼= Km,m; if 1 6∈ 0∗(S)then Cay(G,S) ∼=C|G|
m[K¯m] where|G|>2m. It follows that aiS=ajS for any ai,aj∈S. Thus H=a1−1S is a subgroup of G and S=a1H . This case is as in part (ii).
(3) Suppose that02∗=r≥1. By Lemma 3.1(iii), r≤2. If r=2, then since A1is 2-set- transitive on S, for any u, v∈ S,|0∗(u, v)| =2 and so0∗(u, v)= {uv=vu,u2 =v2}. It follows that a21 =a22and a22=a32, a contradiction. Thus r =1. Since A1is 2-set-transitive on S,|0∗(u, v)| = 1 for any u, v ∈ S. Hence0∗(u, v) = {uv =vu}or{u2 = v2}. By Lemma 3.4(iv), 16∈0∗(u, v)and sow(0∗(u, v))=2.
First assume that there are two elements a,b ∈ S such that 0∗(a,b) = {a2 = b2}. Then 0∗(a) = ∅ and ab 6∈ 0∗(a,b), so ab = cd for some c,d ∈ S\{a,b}. Thus ab∈0∗(x1, . . . ,xi)for some x1, . . . ,xi∈ S where i>2. Since0∗n =0 for 3≤n ≤m−2 shown in (1), i ≥ m−1 and so w(ab) ≥ m−1. Thus0∗m−1 6= 0 or0m∗ 6= 0. Since w(0∗(u, v))=2 for all u, v∈S where u6=v,P
u,v∈Sw(0∗(u, v))=2(m2)=m(m−1). If0m∗−1 =s 6=0 then since AS1 is transitive on S, |0∗(S\{u})| =s for all u ∈ S. Thus w(0∗(S\{u}))=s(m−1)and soP
u∈Sw(0∗(S\{u}))=ms(m−1). Since 16∈0∗(S\{u}), we have
w(02(1))≥ X
u,v∈S
w(0∗(u, v))+X
u∈S
w(0∗(S\{u}))
=(s+1)m(m−1) >m2≥w(02(1)), a contradiction. Thus0∗m−1=0, so0∗m=s6=0 and02(1)=S
u,v∈S0∗(u, v)∪0∗(S)\ {1}. Without loss of generality, suppose that a = a1 and b =a2, and let ai =oiei such that oi∈G20and ei∈G2, where G2is a Sylow 2-subgroup and G20is a Hall 20-subgroup of G.
Since a12=a22, o1=o2=: o and e21=e22. For any ai∈S with i 6=1,2, since a1a2∈0∗(S),
there is an aj such that a1a2 = aiaj. If j =i then oi2 =o1o2 = o2 and e2i = e1e2, so oi =o. If j6=i then since aiaj =a1a2, aiaj6∈0∗(ai,aj). Since0∗(ai,aj)6= ∅, we have 0∗(ai,aj)= {a2i =a2j}. It follows that oi =oj and ei2=e2j. Since aiaj=a1a2=o2e1e2, we have oi = o and eiej = e1e2. Thus, whether j=i or not, we have oi = o and e4i =(eiej)2 =(e1e2)2 =e41. Hence o1 =o2 = · · · =omand e41=e24 = · · · =em4. Note that G = hSi, so G20= hoiand G2 = he1,e2, . . . ,emi. If e41 6= 1 then G2has only one subgroup of order 2. By [14, p. 59], G2is cyclic; if e14=1 then G2is of exponent 4. This case is as in part (v).
Now assume that 0∗(u, v) = {uv}for any u, v ∈ S and that G is not as in part (v).
For any T ⊆ S\{1}, by the previous paragraph, Cay(G,S) ∼= Cay(G,T)implies that 0∗(u0, v0) = {u0v0}for any u0, v0 ∈ T with u0 6= v0. By Lemma 3.3, S is conjugate in Aut(G)to T and so S is a CI-subset. For anyρ∈ A1, let bi =aiρand T = {b1, . . . ,bm}. Then Cay(G,S)=Cay(G,T). By Lemma 3.3,ρinduces an automorphism of G. Thus A1≤Aut(G), so A1 =Aut(G,S)and A=G A1=GoAut(G,S), which is as in part (iv).
(4) Assume that0∗2 =0 and0m∗−1=r≥1. Then m≥4. Since A1is transitive on S, we have|0∗(S\{x})| =r for every x∈S. If r ≥2, then since 16∈0∗(S\{x})for any x∈ S,
w(02(1))≥X
x∈S
w(0∗(S\{x}))=r m(m−1) >m2 ≥w(02(1)),
a contradiction. Thus r=1. Letv(x)be the unique element of0∗(S\{x}). Ifv(a1)=a1, then for any ai, we havev(ai)=aibecause A1is transitive on S. Thus Cay(G,S)∼=Km+1
as in part (i). Now suppose thatv(a1)6=a1. Thenv(a1)∈0(x)for all x ∈ S\{a1}. Let b = a1−1v(a1)and S∗ = S∪ {b}. We shall prove that b−1S∗ is a subgroup of G. To do this, we need to prove that b−1ai·(b−1aj)−1∈b−1S∗for any i6= j . Since i6= j , we may assume that j 6=1. Thenv(a1)∈0(aj)and sov(a1)=ajakfor some ak∈S. Thus
b−1ai·(b−1aj)−1=b−1·b·aia−j1
=b−1·a1−1v(a1)·aia−j1
=b−1·a1−1ajak·aia−j1
=b−1a−11aiak·
If aiak∈0(a1), that is, aiak=a1ak0for some ak0 ∈S, then b−1ai(b−1aj)−1=b−1a−11aiak
=b−1ak0 ∈b−1S∗. Hence H :=b−1S∗is a subgroup of G and S∗is a coset of H . Thus S= S∗\{b} =b H\{b}, and Cay(G,S)=Cay(G,S∗)−Cay(G,{b})∼=C|G|
m+1[K¯m+1]−|Gk|Ck
where k = o(b), which are as in part (iii) of the theorem. Thus, in the following, we only need to prove that aiak ∈ 0(a1). Since i 6= j , aiak 6= ajak = v(a1). If i 6= k, then since0∗n =0 for 2 ≤n ≤m−2, aiak ∈0∗(S)∪0∗(S\{x})for some x ∈ S\{a1} and so aiak ∈ 0(a1). Thus we may assume that i = k, so aiak =ak2. If ak2 =a21 then ak2 ∈ 0(a1). Hence suppose that ak2 6=a21. Since ajak =v(a1)∈ 0∗(S\{a1}), there exist ah,al ∈ S\{aj,ak}such that ajak =ahal. If l =h then ah2 =ajakand so0∗(ah)= ∅. Since A1is transitive on S,0∗(ak)= ∅and so a2k ∈0∗(S)∪0∗(S\{x})for some x ∈ S.
Since ak26=v(a1), we have ak2∈0(a1). If l6=h, then at least one of akahand akaldoes not belong to0∗(S\{aj}), say, akah6∈0∗(S\{aj}). Thus akah∈0∗(S)∪0∗(S\{x})for some x ∈ S\{aj}, and so akah =ajal0 for some l0, which, together with ajak =ahal, implies ak2 = alal0. Thus0∗(ak) = ∅and so a2k ∈ 0∗(S)∪0∗(S\{x})for some x ∈ S. Since ak26=v(a1), ak26∈0∗(S\{a1})and so ak2∈0(a1). This completes the proof of the theorem.
2
Theorem 3.5 gives an application to Babai and Frankl’s question.
Corollary 3.6 Let G be an elementary Abelian p-group, p a prime,and S a Cayley subset. Let A=Aut Cay(G,S). If AS1 ≥Alt(S),then S is a CI-subset of G.
Proof: Since any subgroup of G is still elementary Abelian group and each isomorphism between any two subgroups can be extended as an automorphism of G, we may assume thathSi =G. By Theorem 3.5, Cay(G,S)satisfies parts (i)–(iv). It is easy to check that S
is a CI-subset of G. 2
Remark By Theorem 3.5, the graphs in parts (i)–(iii) have been completely character- ized. The graphs Cay(G,S)in part (iv) satisfies a very strong condition Aut Cay(G,S)≤ GoAut(G)’s.
4. Finite m-DCI p-groups, p a prime
By definition, a finite group G is a 1-DCI group if and only if all elements of G of the same order are conjugate in Aut(G). Suppose that G is a 1-DCI p-group. If p is an odd prime then G is homocyclic by the result of Shult [13]; if p=2 then by [7], G is a homocyclic group or the quaternion group Q8, or G satisfies the following conditions:
(i) G0=8(G)is homocyclic of rank n;
(ii) G/G0is of order 2nor 22n;
(iii) the centre Z(G)of G consists of the identity and all the involutions of G;
(iv) either Z(G)=G0, or CG(G0)=G0with Z(G)=8(G0).
It is easy to see that homocyclic groups and Q8are 1-DCI groups, however, it is still difficult to characterize precisely 1-DCI 2-groups, see [7]. For m ≥2, the problem of determining m-DCI groups is very different from the case m=1. By Lemma 2.4, we need to consider mainly Abelian p-groups. We first prove a property of Cayley graphs of arbitrary Abelian
p-groups.
Proposition 4.1 Let G be an Abelian p-group,S a Cayley subset of G such thathSi =G and A=Aut Cay(G,S). If p26 | |A1|then either S is a CI-subset,or pk |A1|and S contains a coset of some subgroup of G,where A1is the stabilizer of 1 in A.
Proof: Suppose that|G| = pd. If p6 | |A1|, then G is a Sylow p-subgroup of A. By Sylow Theorem and Theorem 2.1, S is a CI-subset. Thus assume that pk |A1|. Let P be a Sylow p-subgroup of A containing G. Then|P : G| = p and P1 ∼=Zp where P1is the
stabilizer of 1 in P, and so P is non-Abelian, see [15, 4.4]. Assume that S is not a CI-subset of G. By Theorem 2.1, there is aτ ∈Sym(G)such that Gτ < A and Gτis not conjugate to G. Let g∈ A such that(Gτ)g < P. Then Gτg 6=G and P ≥ hGτg,Gi>G. Hence P = hGτg,Gi =GτgG as|P : G| = p. Since any element in Gτg∩G commutes with all elements of Gτgand G, we have Gτg∩G≤Z(hGτg,Gi)=Z(P). Further
|Gτg∩G| = |Gτg||G|
|GτgG| = pd· pd
pd+1 = pd−1.
Since P is non-Abelian, Gτg∩G=Z(P). For any a∈Z(P), Pa =P1a =P1a=P1, so P1 fixes all vertices in Z(P). NowhZ(P),P1iis an Abelian subgroup of index p in P. Hence hZ(P),P1iCP andhZ(P),P1ihas orbits{xZ(P)| x ∈ G}on V0=G. Thus P1fixes every xZ(P)setwise. Moreover, P1= hαihas an orbit O on S of length p. If a∈O ⊆S, then since P1 fixes xZ(P)setwise for each x ∈ G, aα ∈ aZ(P), so aα = az for some z∈Z(P). Thus O=ahαi= {a,az,az2, . . . ,azp−1} =ahzi. Thus the proposition holds.
2 This result has been generalized in [8] to general abelian groups under certain conditions.
The following lemma enables us to focus our attention on connected graphs.
Lemma 4.2 Assume that G is a homocyclic p-group and that S is a Cayley subset of G.
If S is a CI-subset ofhSiand for any subset T of G,Cay(hTi,T)∼=Cay(hSi,S)implies hTi ∼= hSi,then S is a CI-subset of G.
Proof: Assume that S is a CI-subset ofhSiand that T is a Cayley subset of G such that Cay(hTi,T)∼=Cay(hSi,S). ThenhTi ∼=σ hSifor some isomorphismσ fromhTitohSi. Let T0=Tσ. Then Cay(hSi,T0)∼=Cay(hTi,T)∼=Cay(hSi,S). Since S is a CI-subset of hSi, there isα∈Aut(hSi)such that T0σ =S. Thusβ =σαis an isomorphism fromhTito hSisuch that Tβ =(Tσ)α =T0α =S. Since G is a homocyclic p-group, it is easy to show that every isomorphism between any two isomorphic subgroups of G can be extended as an automorphism of G. Letρ ∈Aut(G)be an extension ofβ. Then Tρ=Tβ =S, so S
is a CI-subset of G. 2
Now we can determine m-DCI p-groups for 2≤m≤ p+1.
Theorem 4.3 Let G be a finite p-group,where p is prime. Then
(1) G is an m-DCI group for 2≤m≤ p−1 if and only if p≥3 and G is homocyclic; (2) G is a p-DCI group if and only if G is elementary Abelian,cyclic,or G=Q8; (3) G is a(p+1)-DCI group if and only if G is elementary Abelian,or G=Z4,Q8. Proof:
(1) By Lemmas 2.3 and 2.4, we only need to prove that homocyclic p-groups are m-DCI groups. Let S be a Cayley subset of G of size m. By [8, Theorem 1.1], S is a CI-subset ofhSi. Thus by Lemma 4.2, S is a CI-subset of G and G is an m-DCI group.
