The Number of Connected Cayley Graphs over Dicyclic Group

Wang Yongwei Liu Weijun Feng Lihua

(School of Mathematics and Statistics,HNP-LAMA,Central South University,Changsha 410083,China）

Abstract Let p be an odd prime.In this paper,we obtain the number of(connected)Cayley graphs on the dicyclic groups T4p=〈a,b|ap=b4=1,b?1ab=a?1〉up to isomorphism by using the Pólya enumeration theorem.

Key words Cayley graph Dicyclic group Isomorphic class Pólya enumeration theorem

1 Introduction

In this paper,we are interested in a special class of regular graphs–Cayley graphs.

Given a finite groupGand a subsetS?G{1}withS=S?1(suchSis called symmetric),the Cayley graphX(G,S)has vertex setG?two verticesa,binGare called adjacent ifa?1b∈S.IfSgeneratesG,thenX(G,S)is connected.

For a finite groupG,letΓ=X(G,S)for some symmetric subsetS?G.Letσbe an automorphism ofG.Thenσnaturally acts on the vertex setV=G.ForT=σ(S),it is easily shown thatσinduces an isomorphism fromX(G,S)toX(G,T).Such an isomorphism is called a Cayley isomorphism.However,in a general setting,it is also possible that two Cayley graphsX(G,S)andX(G,T)are isomorphic but there are no Cayley isomorphisms mappingStoT.The purpose of this paper is to investigate the conditions under whichX(G,S)～=X(G,T)if and only ifσ(S)=Tfor someσ∈Aut(G).

A Cayley graphX(G,S)is called a CI-graph ofG,if,wheneverX(G,S)～=X(G,T),there is an elementσ∈Aut(G)such thatT=σ(S)(here CI stands for Cayley Isomorphism).A finite groupGis called a CI-group if all the Cayley graphs ofGare CI-graphs.

The investigation of CI-graphs or CI-groups was initiated fromádám[1]in 1976,who proposed the following conjecture:

ConjectureAll circulant graphs are CI-graphs of the corresponding cyclic groups.

This conjecture was turned out to be false as suggested by Elspas and Turner[8].However,it leads to a new research direction on the characterization of CI-graphs or CI-groups[3,5,6,7,10,11,15,18,19].

To determine and enumerate the isomorphic classes of graphs is a foundamental but difficult issue in graph theory[9],this is also the case even we restrict ourselves to the Cayley graphs of a given group(see,for example,[2]),but the latter is closely related to the CI-graphs or CI-groups.From the definition,ifX(G,S)is a CI-graph,then to determine whetherX(G,S)is isomorphic toX(G,T),we need only to see if there exists an automorphismσ∈Aut(G)such thatσ(S)=T.From this point,Mishna[17]applied the Pólya enumeration theorem to count the isomorphic classes of Cayley graphs(Cayley digraphs)on some CI-groups.Also,the isomorphic classes of some families of Cayley graphs which are edge-transitive but not arc-transitive were determined in[16,21,22].For more results on this topic,we refer the reader to the review paper[14]and the references therein.

The Dicyclic group is given by

T4nis a non-abelian group of order 4n,and is also called a binary dihedral group in some other references.In[12],the authors obtained the number of(connected)Cayley graphs on dihedral groupsD2p=〈a,b|ap=1,b2=1,b?1ab=a?1〉(pis an odd prime)up to isomorphism.As mentioned in[4],unlikeD2n,T4nis not a semidirect product of〈a〉and〈b〉for generaln.In[15],Li et al.showed thatT4pis a CI-group any odd primep.This essential result hints us the possibility to enumerate the isomorphic classes of Cayley graphs ofT4p.Borrowing ideas from the works in[17,12],in this paper,we obtain the number of(connected)Cayley graphs onT4pup to isomorphism.

2 Preliminaries

In this section,we will introduce some notations,and also present several conclusions which will be used later.

We use Znandto denote the additive cyclic group of ordern,and the multiplicative group of units of the ring of integers modulon,respectively.For a finite groupG,we use Aut(G)to denote the group of automorphisms ofG.Φ(n)denotes the number of integersi(1≤i≤n)coprime ton.

Definition 2.1LetXbe a set andGa finite group with identitye.An action ofGonXis a map Ψ:G×X→Xdefined by Ψ(g,x)=gxsuch that

(1)ex=x,for allx∈X;

(2)(g1g2)x=g1(g2x),for allx∈Xand allg1,g2∈G.

One says thatGacts onX.WhenGis a permutation group,one can obtain a natural action ofGonXby defininggx=g(x).

Definition 2.2Assume that the groupGacts on a setX.Ifx∈X,then the orbit ofxis the subsetGx={gx|g∈G}ofX.The stabilizer ofxis the subgroup ofGdefined byGx={g∈G|gx=x}.

SupposeGis a permutation group acting on a setXwithnelements.Then every permutationginGhas a unique disjoint cycle decomposition.We define the cycle type ofg∈Gas type(g)={b1(g),b2(g),...,bn(g)},wherebi(g)is the number of cycles of lengthi.For example,the permutation (1532)(46)(87)(9)is of type{1,2,0,1,0,0,0,0,0}.Note thatb1(g)+2b2(g)+···+nbn(g)=n.

The cycle indexZ(G,X)is the polynomial withnvariablesx1,x2,...,xndefined as

For two finite setsDandR,letRDdenote the set of all functions fromDtoR.Suppose thatGis a permutation group acting onD.Then we obtain a group action(G,RD)naturally by setting

for allg∈G,f∈RDandx∈D.Under the group action(G,RD),two maps inRDare said to beG-equivalent if they belong to the same orbit.The Pólya Enumeration Theorem provides the number of orbits of the group action(G,RD).

Lemma 2.1(Pólya Enumeration Theorem,see[9])LetDandRbe two finite sets with|D|=nand|R|=m.LetGbe a permutation group acting onD.Denote byFthe set of all orbits of the group action(G,RD).Then

whereZG(x1,x2,...,xn)is the cycle index of(G,D)defined in(2.1).

Our focus is on the dicyclic group.In general,the presentation for dicyclic groupT4n(see,for example,[4])is given by

For any odd numbern≥3,settingx2=aandt=b,then we have

This group has order 4n,and

Lemma 2.2For the dicyclic groupT4n=〈a,b|an=b4=1,b?1ab=a?1〉,wheren≥3 is odd,we have

(1)akb=ba?k;akb2=b2ak;akb3=b3a?k;

(2)(akb)?1=akb3;(akb2)?1=a?kb2.

ProofBy the relationsan=b4=1 andb?1ab=a?1,the results follow immediately.

Lemma 2.3([15])For an odd numbern,letT4n=〈a,b|an=b4=1,b?1ab=a?1〉be the dicyclic group and Z(T4n)be its center.Then for each automorphismσ∈Aut(T4n),we haveσ(b)=aβb1+rfor someβ∈Zn,wherebr∈Z(T4n).

By Lemma 2.3,the automorphism group of the dicyclic groupT4ncan be described.

ProofThe automorphism of cyclic group〈a〉isσ(a)=ai,where gcd(i,n)=1.Since Z(T4n)={1,b2},by Lemma 2.3,for each automorphismσofT4n,we haveσ(b)=aβborσ(b)=aβb3,whereβ∈Zn.Define

and

It is easy to verify thatσα,β,τγ,δ∈Aut(T4n).By the preceding paragraph,we have Aut(T4n)=

For an odd primep,Li et al[15]showed that the dicyclic group is a CI-group.This crucial result is very helpful in our study.From this observation,we have

Lemma 2.4LetX(T4p,S)andX(T4p,T)be two Cayley graphs onT4p.ThenX(T4p,S)～=X(T4p,T)if and only if there exists someσ∈Aut(T4p)such thatσ(S)=T.

3 Enumerating Cayley Graphs on T4p

Now we turn our attention to the Cayley graphX(T4p,S),wherepis an odd prime.SinceS=S?1,we may assume thatD=A∪B,whereA=A1∪A2∪{b2},and

Then Aut(T4p)acts onDnaturally by setting

and

for eachσα,β,τγ,δ∈Aut(T4p).

Sinceτγ,δ(ajb)=ajγ+δb3,thus we need only find those automorphisms inthat fix every element ofA.

Letσα,β(akb)=akbfor eachk∈Zp.Takek=0,we haveσα,β(a0b)=aβb=a0b,which implies thatα=0.Take somej=j0∈Zp{0},then

which gives thatj0α=j0,thusSoσ1,0is the identity element of Aut(T4p).This implies that Aut(T4p)acts onDfaithfully.Also observe thatσα,β(A)=A,σα,β(B)=Bandτγ,δ(A)=A,τγ,δ(B)=Bfor eachσα,β,τγ,δ∈Aut(T4p).LetR={0,1}.Then Aut(T4p)is a permutation group acting onDandRD.

ForS?D,letfSdenote the characteristic function ofS,that is,fS(a)=1 ifa∈S,andfS(a)=0 ifa∈DS.Clearly,fS∈RDandRDconsists of all characteristic functions onD.By Lemma 2.4,we know that two Cayley graphsX(T4p,S)andX(T4p,T)onT4pare isomorphic if and only if there exists someσ∈Aut(T4p)such thatσ(S)=T,which is the case if and only iffS,fT∈RDare Aut(T4p)-equivalent.Thus the number of Cayley graphs onT4pup to isomorphism is equal to the number of orbits of the group action(Aut(T4p),RD).Therefore,by Lemma 2.1,in order to enumerate Cayley graphs onT4p,we first need to compute the cycle index of the permutation group Aut(T4p)acting onD.

Also,sincepis an odd prime,we know thatis a cyclic group of orderp?1.Thus we can assume thatfor some integerz∈Zp{0}.Then for anythere exists someiα∈Zp?1such thatα=ziα.Furthermore,ifαranges over all elements oftheniαranges over all elements of Zp?1.

The following lemma plays a crucial role to the calculation of cycle index.

Lemma 3.1LetD=A∪Bandσα,β,τγ,δ∈Aut(T4p)be defined as above.And letUnder the action of Aut(T4p)onD,the cycle type ofσα,β,τγ,δis given by type(σα,β)={b1(σα,β),b2(σα,β),...,b2p(σα,β)}and type(τγ,δ)={b1(τγ,δ),b2(τγ,δ),...,b2p(τγ,δ)},where

ProofSince

and

we must have

and

Forσα,β,τγ,δ∈Aut(T4p),we consider the following two cases.

Case 1:α=1(γ=1)?

Observe thatforwe see the permutationσ1,βsplitsAintopcycles of length 1.Also note thatfor 0≤j≤p?1.Ifβ=0,thenfor eachj,and soσ1,0splitsBintopcycles of length 1.Ifβ∈Zp{0},the order ofβ∈Zpiso(β)=p.Then,for anyis in the cycle

Thus the permutationσ1,βsplitsBinto exactly one cycle of lengthp.Therefore,we obtain the cycle type ofσ1,β.

Similarly,we can obtain that the cycle type ofτ1,δis the same as the cycle type ofσ1,β.

Thus we obtain the cycle type ofσ1,βandτ1,δ,as shown in(3.6).

Case 2:

Observe that

Firstly,we claim thatσα,βhas the same cycle type asσα,0for eachβ∈Zp.

Since

and

and

for eachl∈Zr.Thus(φ(ˉak1b),φ(ˉak2b),···φ(ˉakrb))is a cycle ofσα,β.Therefore,σα,βandσα,0also have the same cycle type inBbecauseφis a bijection.So the claim holds.

Hence,we just need to consider the cycle type ofσα,0inD=A∪B.

Firstly,sinceσα,0(b2)=b2,the permutationσα,0splits{b2}into one cycle of length 1.

For any fixedˉai∈A1,assume thatN(α)is the minimal positive integer such that

Then we have

or

Then we have obtained the cycle type ofσα,β,as shown in(3.7).

Similarly,we can obtain the cycle type ofτγ,δ,as shown in(3.8).

The proof is complete.

Lemma 3.2LetD=A∪B.The cycle index of Aut(T4p)acting onDis given by

ProofBy Lemma 3.1,the cycle index of Aut(T4p)acting onDis given by

This completes the proof.

According to Lemmas 2.1 and 3.2,we can obtain the number of Cayley graphs onT4pup to isomorphism immediately.

Theorem 3.1Letpbe an odd prime.The number of Cayley graphs onT4pup to isomorphism is equal to

In[17],Mishna also enumerated the circulant graphs of orderpup to isomorphism.

Lemma 3.3([17])Letpbe an odd prime.The number of circulant graphs of orderpup to isomorphism is equal to

where Φ is Euler’s totient function.

From Theorem 3.1 and Lemma 3.3,we can also give the number of connected Cayley graphs onT4pup to isomorphism.

Theorem 3.2Letpbe an odd prime.The number of connected Cayley graphs onT4pup to isomorphism is equal to

where NTand NCare presented in(3.10)and(3.11),respectively.

ProofIt is well known that a Cayley graphX(G,S)is connected if and only if〈S〉=G.Thus,forS?T4p{0},the Cayley graphX(T4p,S)is disconnected if and only ifS?A=A1∪A2∪{b2}=〈a〉∪〈a〉b2{0}orS={ajb,ajb3}orS={b2,ajb,ajb3}forj∈Zpbecausepis a prime.

IfS1?A1=〈a〉,then by Lemma 3.3,there are NCisomorphic classesS1inA1.Similarly,Ifthen there are NCisomorphic classesS2inA2.And ifS1?=?andS2?=?,thenS1∪S2is the isomorphic class inA1∪A2,thus there are(NC?1)2such isomorphic classes inA1∪A2.Therefore?,S1,S2andS1∪S2are isomorphic classes inA1∪A2,where??=S1?A1and??=S2?A2.Thus there areisomorphic classes inA1∪A2.Moreover,we have{b2},S1∪{b2},S2∪{b2}andS1∪S2∪{b2}are isomorphic classes inA1∪A2{b2},wherethen there areisomorphic classes inA1∪A2∪{b2}.Summing up the above,we have 2N2Cisomorphic classes inA.

Also note that{b2,b,b3}),then there are 2 isomorphic classes such that the Cayley digraphX(T4p,S)is disconnected,whereS?B.

Hence,from Theorem 3.1 and the above,we have that the number of connected Cayley graphs onT4pup to isomorphism is equal to

This completes the proof.

Example 3.1Takep=3 and consider the dicyclic groupT12={a,b|a3=1,b4=1,b?1ab=a?1}.LetD=T12{e}.Then it is easy to see that there are 32 representative elements of Aut(T12)-equivalent classes of subsets ofD.

Moreover,Cayley graphX(T12,S)is disconnected,ifSis one of

Cayley graphX(T12,S)is connected,ifSis one of

Thus there are exactly 22 connected Cayley graphs onT12up to isomorphism.By Lemma 3.3 and Theorems 3.1,and 3.2,we have

At the end of this paper,we list the number of connected Cayley graphs onT4p(pis a prime)up to isomorphism for 3≤p≤19 by applying Theorem 3.2(see Tab.1).

Table 1 The number of Cayley graphs on T4p(3≤p≤19)