Classifying Arc-Transitive Circulants of Square-Free Order
CAIHENG LI∗
Department of Mathematics and Statistics, University of Western Australia, Nedlands, WA 6907, Australia
DRAGAN MARU ˇSI ˇC†
IMFM, Oddelek za matematiko, Univerza v Ljubljani, Jadranska 19, 1000 Ljubljana, Slovenia
JOY MORRIS
Department of Mathematics and Statistics, Simon Fraser University, Burnaby, BC, Canada, V5A 1S6 Received July 15, 1999; Revised May 2, 2001
Abstract. Acirculantis a Cayley graph of a cyclic group. Arc-transitive circulants of square-free order are clas- sified. It is shown that an arc-transitive circulantof square-free ordernis one of the following: the lexicographic product[K¯b], or the deleted lexicographic[K¯b]−b, wheren=bmandis an arc-transitive circulant, or is anormalcirculant, that is, Authas a normal regular cyclic subgroup.
Keywords: circulant graph, arc-transitive graph, square-free order, cyclic group, primitive group, imprimitive group
1. Introductory remarks
Throughout this paper, graphs are simple and undirected; the symbolZn, where n is an integer, will be used to denote the ring of integers modulonas well as its (additive) cyclic group of ordern.
Letbe a graph andGa subgroup of its automorphism group Aut. The graphis said to beG-arc-transitiveifGacts transitively on the set of arcs of. In particular,is said to be arc-transitiveifis Aut-arc-transitive. Note that an arc-transitive graphis necessarily vertex-transitive, that is, its automorphism group acts transitively on the vertex setVof. Given a groupGand a symmetric subsetS=S−1ofGwhich does not contain the identity ofG, theCayley graph of G relative to S, denoted by Cay(G,S), has vertex setGand edges of the form{g,gs}, for allg ∈Gands∈S. By the definition, the groupGacting by right multiplication is a subgroup of Autand acts regularly on V=G. The converse also holds (see [6]). Acirculantis a Cayley graph of a cyclic group. Thus a graphis a circulant of ordernif and only if Autcontains a cyclic subgroup of ordernwhich is regular onV.
∗Li is grateful to the Institute of Mathematics, Physics and Mechanics at the University of Ljubljana for hospitality and financial support during his visit that led to the completion of this work.
†Supported in part by the “Ministrstvo za znanost in tehnologijo Republike Slovenije,” project no. J1-101-04965-99.
A classification of 2-arc-transitive circulants was given in [1]. (A sequence(u, v, w)of distinct vertices in a graph is called a 2-arcifu, ware adjacent tov; a graphis said to be 2-arc-transitiveifAutis transitive on 2-arcs of.) It was proved that a connected, 2-arc-transitive circulant of ordern,n≥3, is one of the following graphs: the cycleCn, the complete graphKn, the complete bipartite graphKn2,n2,n≥6, orKn2,n2−n2K2wheren2 ≥5 odd (the complete bipartite graphKn2,n2 minus a 1-factor).
In this paper we take the next step in our pursuit of a classification of all arc-transitive circulants, by classifying all such graphs of square-free order. To describe this classification, a few words on the notation are in order. For two graphsand, denote by[] the lexicographic product of by, that is, the graph with vertex setV×Vsuch that (u1, v1)is adjacent to(u2, v2)if and only if eitheru1is adjacent in tou2, oru1 =u2
andv1is adjacent intov2. If in addition,andhave the same vertex set then denote by−the graph with vertexVand having two vertices adjacent if and only if they are adjacent inbut not adjacent in. Furthermore, let¯ denote the complement of, and for a positive integerm, denote bym the graph which consists ofmdisjoint copies of. A circulantis called anormal circulantif Autcontains a cyclic regular normal subgroup. The following is the main result of this paper.
Theorem 1.1 Letbe an arc-transitive circulant graph of square-free order n. Then one of the following holds:
(1) is a complete graph;
(2) is a normal circulant graph;
(3) =[K¯b]or=[K¯b]−b,where n=mb,andis an arc-transitive circulant of order m.
Remark 1.2 Letbe a connected arc-transitive circulant. If=[K¯b] or if=[K¯b]− b, then the graphmay be easily reconstructed from a smaller arc-transitive circulant . Thus the graphs in part (3) of Theorem 1.1 are well-characterized. As for arc-transitive normal circulants, the following observations are in order. For two groupsGandH, denote by G·H an extension ofG by H, and denote byG H a semidirect product ofG by H. Assume that=Cay(R,S)is normal. Let Aut(R,S)= {σ ∈Aut(R)| Sσ=S}. Then by [4, Lemma 2.1], Aut=R Aut(R,S), and since is arc-transitive, Aut(R, S)is transitive onS. ThusSmay be written as{sσ |σ ∈Aut(R,S)}wheres∈S, that is,Sis an Aut(R,S)-orbit under the Aut(R)-action. AsRis cyclic,s = Rif and only ifS = R.
Hence, since is connected,sgenerates R. This provides us with a general method for constructing connected arc-transitive normal circulants, that is, for any generating element g of R and a subgroup H of Aut(R), Cay(R,gH)is a connected arc-transitive normal circulant. Note that, sinceRis cyclic, Aut(R)is abelian.
2. Proof of Theorem 1.1
This section is devoted to proving Theorem 1.1. We use a standard notation and terminology, see for example [3]. Letbe a finite graph, and assume thatG ≤ Autis transitive on
V. LetB= {B1,B2, . . . ,Bm}be aG-invariant partition ofV, that is, for eachBi and eachg∈G, either Big∩Bi= ∅, orBig=Bi. A partitionBis called arefinedpartition of a partitionBif a block ofBis a proper subset of a block ofB. For B∈B, denote byGB
the subgroup ofG which fixes B setwise, and byGBB the permutation group induced by GB onB. Thekernel NofG onBis the subgroup ofG in which every element fixes all B ∈B. Clearly,Nis a normal subgroup ofG. A partitionBis said to beminimalifBhas no refined partitions. It follows that ifBis a minimal partition of, thenGBB is primitive for each block B ∈ B. For aG-invariant partitionBof V, thequotient graphB of induced onBis the graph with vertex setBandBiis adjacent inBtoBj if someu ∈ Bi
is adjacent into somev ∈ Bj. Two blocksB,B∈Bare said to be adjacent if they are adjacent inB; denote by[B,B] the subgraph ofwith vertex setB∪Band with two vertices adjacent if and only they are adjacent in.
As in Theorem 1.1, letn be a positive square-free integer, and letbe an arc-transitive circulant of ordern. We will complete the proof of Theorem 1.1 by proving the following proposition, which is slightly stronger than Theorem 1.1.
Proposition 2.1 Letbe a G-arc-transitive circulant of square-free order,where G ≤ Autand let R be a cyclic regular subgroup of G. Then one of the following statements holds.
(1) G is2-transitive on V,andis a complete graph;or (2) R is normal in G;or
(3) there exists a minimal G-invariant partitionBof Vsuch that for the kernel N of the G-action onBand for a block B∈B,either
(i) N is not faithful on B and=B[K¯b],or
(ii) K ∼=KBis2-transitive on B and=B[K¯b]−bB.
The proof of this proposition consists of a series of lemmas. As in the proposition, we denote byGa subgroup of Autwhich is transitive on the set of arcs of, and byRa cyclic subgroup ofG. First, assume thatGis primitive onV. Then by Schur’s theorem (see [3, Theorem 3.5A, p. 95]), eitherG is 2-transitive, or|V| = pandZp ≤ G≤ Zp Zp−1
for some prime p. Thus we have the following lemma.
Lemma 2.2 If G is primitive on V,then eitheris complete, or R is normal in G.
Hence we assume thatGis imprimitive onVin the rest of this section.
Lemma 2.3 LetBbe a minimal G-invariant partition of V,and let N be the kernel of the G-action onB. Take B ∈ B,and let NB be the permutation group induced by N acting on B. Then either NB is2-transitive,orZp ≤NB ≤Zp Zp−1,where B∈B;in particular,in both cases NBis primitive.
Proof: It is clear that GBB is primitive, NBGBB, and N contains the subgroup of R of order |B|. Thus NB and soGBB contains a cyclic regular subgroup on B. By Schur’s
theorem, eitherGBB is 2-transitive, orZp≤GBB≤Zp Zp−1. By Burnside’s theorem (see [3, Theorem 4.1B, p. 107]), if GBB is 2-transitive then soc(GBB)is nonabelian simple or elementary abelian. It then follows, sincen is square-free, that eitherT ≤ GBB≤Aut(T) for some nonabelian simple groupT, orZp≤GBB≤Zp×Zp−1. IfZp≤GBB≤Zp Zp−1, then we have Zp≤NBGBB≤Zp Zp−1. Assume that T≤GBB≤Aut(T)with T non- abelian simple. ThenT is transitive, and furthermore,NBcontainsT. Suppose thatNBis imprimitive onB. Then there exists aNB-invariant partitionBof Bsuch that the regular cyclic subgroup (on B) of NB is transitive and not faithful onB. Thus NB has a nor- mal subgroup which is intransitive on B, which is not possible since T is the unique minimal normal subgroup of GBB and transitive on B. Hence NB is primitive, and so
2-transitive. ✷
Next we deal with two different cases according to the actions ofNon a blockB∈B. Lemma 2.4 Assume that there exists a minimal G-invariant partitionBof Vsuch that N is not faithful on B, where N is the kernel of the G-action onB, and B∈B. Then =B[K¯b],where b= |B|;as in part(3) (i).
Proof: LetMbe the kernel of theN-action onB. Then 1=MN, and so 1=MBNB for some B∈B. Since NB and NB are isomorphic as permutation groups and NB is primitive (by Lemma 2.3), it follows thatMBis transitive onB. Asis connected, there exists a sequence of blocksB0=B,B1, . . . ,Bl=Bsuch that a vertex inBjis adjacent in to some vertices inBj+1for each 0≤j≤l−1, and there exists 0≤i<lsuch thatMBj=1 for all j≤i andMBi+1=1. Then foru∈Bi,MBi∪Bi+1is transitive on{{u, v} |v∈Bi+1}.
SinceNBi∪Bi+1is transitive onBiand fixes Bi+1(setwise), each vertex inBiis adjacent to all vertices inBi+1. It follows that=B[K¯b], whereb= |B|. ✷ Lemma 2.5 Assume that there exists a minimal G-invariant partition B of V such that N ∼= NB is2-transitive on B,where N is the kernel of G on B,and B∈B. Then =B[K¯b]−bB,where b= |B|;as in part(3) (ii).
Proof: We note that, sinceis a circulant, we may label the vertices ofby elements ofZn, in such a way that=Cay(R,S), whereS ⊆Zn\{0}satisfiesi∈S if and only if n−i∈S. The subsetSwill be called asymbolof.
We are now going to distinguish two different cases, depending on whether the actions of the groupN on the blocks inBare permutationally equivalent or not. (Recall that by [3, Lemma 1.6B, p. 21] two transitive actions of a permutation group on two sets are equivalent if and only if the point stabilizer of the action on the first set coincides with the stabilizer of a point in the action on the second set.)
Case 1 The actions of Non the blocks inBare equivalent.
It follows that for each block B∈B, there exists v∈B such that Nv=Nv, where v ∈ B. Let Equiv(v)denote the collection of all such verticesv, that is, Equiv(v)= {v∈ V|Nv=Nv}. Then the 2-transitivity of the action ofNon each of the blocks inBimplies
that the stabilizer Nv has two orbits in B, namely{v}and B\{v}, or in other words, B∩Equiv(v)andB\Equiv(v). In particular,|Equiv(v)∩B| =1 for eachB∈B.
Assume first that (v)∩ Equiv(v) = ∅, where (v) denotes the set of neighbors of v. Because of arc-transitivity we have that the bipartite graph induced by a pair of adjacent blocks is a perfect matching. Moreover, it may be seen that(v)⊆Equiv(v). But Equiv(u)=Equiv(v)for anyu∈Equiv(v)and so the subgraph induced by the set Equiv(v) is a connected component of , isomorphic toB, a contradiction to the fact thatis connected andb=1.
Assume now that (v)∩Equiv(v)= ∅. Then for a block B adjacent to B we must have that(v)∩B=B\Equiv(v)=B\{v}. Letdenote the graph obtained fromby joining two non-adjacent vertices ofif and only if they belong to two adjacent blocks in B. In view of the comments of the previous paragraph∼=bBand so=B[K¯b]−bB.
Case 2 The actions of Non the blocks inBare not (all) equivalent.
Using the classification of 2-transitive groups (see [3, Section 7.7]) we deduce that a group can have at most two inequivalent 2-transitive actions (of the same degree). Hence the setBdecomposes into subsetsB0andB1such that the actions ofN on BandB∈B are equivalent whenB∈B0and inequivalent whenB∈B1. Moreover, in view of the fact that is arc-transitive and thus the bipartite graphs induced by pairs of adjacent blocks are all isomorphic, it follows that {B0,B1} is a bipartition of VB with|B0| = |B1|. In particular,|B| =mis an even number. Letρbe a generator of the cyclic regular groupR of G. Letting Bi=Bρi, we have thatB0 consists of all the blocks Bi withi∈Zm even andB1consists of all the blocksBiwithi∈Zmodd. Letvij=ρi+mj, for alli∈Zmand all
j∈Zb.
Now the quotient graphB is a circulant. Assume that 2i+1 belongs to the symbol of B. (Note that the symbol ofBcontains only odd numbers.) Letσ=ρ2i+1and consider the blocksB0,B2i+1andB4i+2. LetT be the subset ofZbconsisting of all thosetsuch that v=v00is adjacent tov2it+1. Thenv02i+1=vσis adjacent to(v2it+1)σ=vσρ2i+1+mt=vρ4i+2+mt= vt4i+2, wheret∈T. Therefore
v2ij+1∼vl4i+2⇔l−j∈T. (1)
Leta∈Zbbe such thatNv=Nu, whereu=v4ia+2. Recall that the bipartite graphs induced by pairs of adjacent blocks are isomorphic, and moreover by the classification of 2-transitive groups [3, Section 7.7],Nvhas two orbits of different cardinalities onB2i+1. Henceuandv must have the same neighbors in B2i+1and so(u)∩B2i+1= {vt2i+1 |t∈T}. Combining this together with (1) we have thata−t∈T for eacht∈T and so
a−T=T. (2)
Now because of the 2-transitivity of the action of N on each block, it follows that
|(v00)∩(v0j)∩ B2i+1| is constant for all j∈Zb\{0}. This implies the existence of a
positive integerλsuch that|T∩(T +j)| =λ, for all j∈Zb\{0}. Hence, in view of (2),
|T ∩(−T+a+j)| =
λ ifj = −a,
|T| ifj= −a. (3)
We now make the following observation about the intersection T ∩(−T +l). (See also [1, Lemma 2.1].) Wheneverx∈T∩(−T+l)there must exist somey∈T such that x= −y+l. Clearly, we get thaty∈T∩(−T +l)by reversing the roles ofxandy. So the elements in the intersectionT∩(−T+l)are paired off with one exception occuring when l∈2T. Then the equalityl=2x(x∈T)gives rise to a unique element in the intersection T∩(−T+l). Therefore the parity of|T∩(−T+l)|depends solely on whetherlbelongs to 2T or not. More precisely,|T∩(−T+l)|is an odd number ifl∈2T and an even number if l ∈/ 2T. Combining this fact with (3) we see that, in particular, Zb\{−a} is either a subset of 2T or ofZb\2T. But then in the first case|T| = |2T| =b−1 and in the second case|T| = |2T| =1. In both cases, a contradiction is derived from the assumption that the actions ofNonB0andB2i+1are inequivalent, completing the proof of Lemma 2.5. ✷ Remark 2.6 Letbe a bipartite graph with parts1and2. Assume that some subgroup G≤Autacts 2-transitively and inequivalently on1 and2. Thenis isomorphic to the incidence graph of a symmetric block design with a 2-transitive automorphism group, and thus such graphs are classified in [5]. By the proof of Lemma 2.5, such a graphis not isomorphic to a bipartite graph induced by two adjacent blocks of imprimitivity of the automorphism group of an arc-transitive circulant of square-free order.
In view of Lemmas 2.2, 2.3, 2.4 and 2.5 above, to complete the proof of Proposition 2.1, we may assume that
for each minimal G-invariant partitionX of V,letting F be the kernel of G on X and X∈X,F ∼=FX is not2-transitive on X.
Now let Bbe a minimal G-invariant partition of V, and let N be the kernel of the G-action onB. Take a blockB∈B. Then by Lemma 2.3,
Zp≤N ∼=NB <Zp Zp−1,
wherepis a prime. LetM=soc(N), which is isomorphic toZp. ThenMG.
Lemma 2.7 There is a subgroup H ofZp−1and a group C such that G=(M×C)·H and M≤R≤M×C.
Proof: Takev∈V, and denote by Gv the stabilizer of v in G. Let P be a Sylow p-subgroup ofGv. Sincen is square-free, p|P|is the maximal power of pdividing|G|, and soM,P =M Pis a Sylowp-subgroup ofG, that is, a Sylowp-subgroup ofGis a split extension ofM byP. By [7, Theorem 8.6, p. 232],Gis a split extension ofM by a subgroupLofG, whereL ∼=G/M, that is,G=M L. LetC=CL(M). ThenM∩C=1,
CG, andG/(MC)is isomorphic to a subgroup of Aut(M)which is isomorphic toZp−1. ThusG=(M ×C)·H, where H≤Zp−1. Since Ris abelian and M < R, we have that
R<CG(M)=M×C. ✷
We are now ready to complete the proof of Proposition 2.1.
Proof of Proposition 2.1: By Lemma 2.7,G=(M0×C0)·H0such thatM0≤R≤M0× C0andH0≤Zp0−1, where p0is a prime. In particular,C0is normal inGand intransitive onV. IfC0=1, thenR=M0is normal inG, as required. Assume thatC0=1. LetC1be the set of theC0-orbits inV. ThenC1is aG-invariant partition ofV. LetB(1)be a mini- malG-invariant partition ofVwhich is a refined partition ofC. Take a blockB(1)∈B(1). LetN1be the kernel ofGonB(1), and letM1=soc(N1). By our assumption,Nis faithful and is not 2-transitive onB(1). Then by Lemma 2.3,M1∼=Zp1for some prime p1. By Lemma 2.7,G=(M1×C1)·H1such thatM1≤R≤M1×C1. NowM0×M1≤R≤(M0×C0)∩ (M1×C1). It follows thatR≤(M0×C0)∩(M1×C1)=M0×M1×C1, andG=(M0× M1×C1)·H1. If C1=1, then R=M0×M1 is normal inG, as required. Assume that C1 =1, and assume inductively thatG=(M0×M1× · · · ×Mi×Ci)·Hisuch thati ≥1, Zpj ∼= Mj≤R for each j, and R≤M0×M1× · · · ×Mi×Ci. NowCiis normal in G and intransitive onV, and hence we may repeat our arguments withCiin place ofC0so that we haveG=(Mi+1×Ci+1)·Hi+1 such thatMi+1 ∼=Zpi+1for some prime pi+1, and Mi+1≤R≤Mi+1×Ci+1. SinceM0,M1, . . . ,Mi+1≤R≤(M0×M1× · · · ×Mi×Ci)∩ (Mi+1×Ci+1), it follows thatR≤(M0×M1× · · · ×Mi×Ci)∩(Mi+1×Ci+1)=(M0× M1× · · · ×Mi+1×Ci+1)such that G=(M0×M1× · · · ×Mi×Mi+1×Ci+1)·Hi+1. Therefore, repeating this argument, we finally obtainG=(M0×M1× · · · ×Mk)·Hsuch that R=M0×M1× · · · ×Mk, which is normal inG, as required. ✷ In view of the comments in the paragraph preceding the statement of Proposition 2.1, this completes the proof of Theorem 1.1.
References
1. B. Alspach, M.D.E. Conder, D. Maruˇsiˇc, and M.Y. Xu, “A classification of 2-arc-transitive circulants,”J. Alg.
Combin.5(1996), 83–86.
2. N. Biggs,Algebraic Graph Theory, Cambridge University Press, London, New York, 1992.
3. J.D. Dixon and B. Mortimer,Permutation Groups, Springer-Verlag, New York, 1996.
4. C. Godsil, “On the full automorphism group of a graph,”Combinatorica1(1981), 243–256.
5. W. Kantor, “Classification of 2-transitive symmetric designs,”Graphs Combin.1(1985), 165–166.
6. G.O. Sabidussi, “Vertex-transitive graphs,”Monatsh. Math.68(1964), 426–438.
7. M. Suzuki,Group Theory I, Springer-Verlag, Berlin, New York, 1982.
