GRAPHS WITH 2N +6 VERTICES AND CYCLIC AUTOMORPHISM 5 1 GROUP OF ORDER 2N 0 2 PETERIS DAUGULIS∗ r p A Abstract. The problem of finding upper bounds for minimal vertex number of graphs with a givenautomorphismgroupisaddressedinthisarticleforthecaseofcyclic2-groups. Weshowthat 2 foranynatural n≥2thereisanundirectedgraphhaving2n+6verticesandautomorphismgroup cyclic of order 2n. This confirms anupper bound claimedby other authors forminimal number of O] verticesofundirectedgraphshavingautomorphismgroupZ/2nZ. C . Key words. graph,automorphismgroup h t a m AMS subject classifications. 05C25,05E18,05C35,05C75. [ 2 1. Introduction. v 7 Representation theories of groups can be divided into two overlapping parts. 3 There are injective representation theories (such as permutation representations and 9 linear representations) which deal with injective homomorphisms G→Aut(X), typ- 6 0 ical problems in this area are classifications and properties of representations (mod- . ules). There are also bijective representationtheories (such as Euclidean space isom- 1 0 etry and graph automorphism theories) which deal with bijective homomorphisms 5 G → Aut(X) and study full automorphism groups of certain objects. Examples of 1 problemsinthislatterareaareproblemsaboutextremalparametervaluesforobjects : v having given automorphism groups. i X This article addresses a problem in graphrepresentationtheory of finite groups- r a findingundirectedgraphswithagivenfullautomorphismgroupandminimalnumber of vertices. All graphs in this article are undirected and simple. It is known that finite graphs universally represent finite groups: for any finite group G there is a finite graph Γ = (V,E) such that Aut(Γ) ≃ G, see Frucht [10]. The problem of finding graphs having a specific automorphism group and minimal number of vertices or orbits is an immediate problem in extremal combinatorics. It was proved by Babai [2] constructively that for any finite group G (except cyclic groups of order 3,4 or 5) there is a graphΓ such that Aut(Γ)≃G and |V(Γ)|≤2|G| (there are 2 G-orbits having |G| vertices each). For certain group types such as ∗Department of Mathematics, Daugavpils University, Daugavpils, LV-5400, Latvia (pe- [email protected]). 1 2 P.Daugulis symmetric groups Σn, dihedral groups Dn and elementary abelian 2-groups(Z/2Z)n graphs with smaller number of vertices (respectively, n, n and 2n) are known. It is easy to construct graphs with 9n vertices having automorphism group (Z/3Z)n and,moregenerally,graphswith 2mnverticeshavingautomorphismgroup(Z/mZ)n with m ≥ 6. In the recent decades the problem of finding µ(G) = min |V(Γ)| Γ:Aut(Γ)≃G for specific groups G does not seem to have been very popular. See Babai [3] and Cameron [6], for expositions of this area. Graphs with abelian automorphismgroups have been investigated in Arlinghaus [1]. For Z/4Z the Babai’s bound for vertices is not sharp: there are 10-vertexgraphs having automorphism group Z/4Z, this fact is mentioned in Bouwer and Frucht [5] and Babai [2], such graphs have been recently described in Daugulis [7]. It implies existenceofgraphswith10nverticeshavingautomorphismgroups(Z/4Z)n.Thereare 12 such 10-vertexgraph isomorphismtypes, 6 types up to complementarity. In these cases there are 3 orbits. For Z/6Z the bound is not sharp also - there are 11-vertex graphs (even disconnected) having this automorphism group: for example, if graph ∆ is such that Aut(∆)≃Z/3Z and |V(∆)|=9, then Aut(∆∪K )≃Z/6Z. 2 In a textbook of Harary [11] there is an exercise claiming (referring to Merri- wether) that if G is a cyclic group of order 2n, n ≥ 2, then the minimal number of graph vertices is 2n+6. In this paper we exhibit such graphs. In this paper we show that the bound µ(G)= min |V(Γ)|≤2|G| Γ:Aut(Γ)≃G is not sharp for G ≃ Z/2nZ, for any natural n ≥ 2. Namely, for any n ≥ 2 there is an undirected graphΓ on 2n+6 vertices such that Aut(Γ)≃Z/2nZ. The number of orbitsis3. Inthis paperwearenotconcernedwithminimizationofnumberofedges. Weusestandardnotationsofgraphtheory,seeDiestel[9]. Adjacencyofverticesi andj isdenotedbyi∼j,anundirectededgebetweeni∼j isdenotedby(i,j). Fora graphΓ=(V,E)thesubgraphinducedbyX ⊆V isdenotedbyΓ[X]: Γ[X]=Γ−X. Theset{1,2,...,n}isdenotedbyVn andtheundirectedcycleonnverticesisdenoted by Cn. The cycle notation is used for permutations. 2. Main result. 2.1. The graph Γm. Definition 2.1. Let n ≥ 2, n ∈ N, m = 2n. Let Γm = (Vm+6,Em+6) be the graph given by the following adjacency description. We define 8 types of edges. 1. i∼i+1for all i∈Vm−1 and 1∼m. (It indicates that Γm[1,2,...,m]≃Cm). Graphswith2n+6verticesandcyclicautomorphismgroupoforder2n 3 2. m+1∼i with i∈Vm iff i≡1 or 2(mod 4). 3. m+2∼i with i∈Vm iff i≡2 or 3(mod 4). 4. m+3∼i with i∈Vm iff i≡3 or 0(mod 4). 5. m+4∼i with i∈Vm iff i≡0 or 1(mod 4). 6. m+5∼i with i∈Vm iff i≡1(mod 2). 7. m+6∼i with i∈Vm iff i≡0(mod 2). 8. m+1∼m+5∼m+3, m+2∼m+6∼m+4. 9. There are no other edges. Definition 2.2. Denote O ={1,2,...,m}, O ={m+1,m+2,m+3,m+4}, 1 2 O ={m+5,m+6}. 3 Remark 2.3. Γm has 4m+4 edges. Its degree sequence is 5m(m +1)4(m +2)2: 2 2 1. vertices in O have degree 5, 1 m 2. vertices in O have degree +1, 2 2 m 3. vertices in O have degree +2. 3 2 Remark 2.4. We can visualize Γm in the following way: 1. Γm[O1] is a cycle which is drawn in a central plane P. 2. Γm[O1,m+1,m+3,m+5] and Γm[O1,m+2,m+4,m+6] are drawn above and below P. 2.2. Special cases. 2.2.1. n=2. The graphwith automorphism group Z/4Z and minimal number of vertices (10) andedges(18)hasbeenexhibitedinBouwerandFrucht[5],p.58. Γ hasbeenrecently 4 describedinDaugulis [7]. Itis shownonFig.1. Itcanbe thoughtasembedded inthe 3D space,it is planar but a plane embedding is not givenhere. Aut(Γ )≃Z/4Z and 4 it is generated by the vertex permutation g =(1,2,3,4)(5,6,7,8)(9,10). There are 3 Aut(Γ )-orbits - {1,2,3,4}, {5,6,7,8},{9,10}. 4 Subgraphs Γ [1,2,3,4,5,7,9] and Γ [1,2,3,4,6,8,10] which can be thought as 4 4 being drawn above and below the orbit {1,2,3,4} are interchanged by g. 4 P.Daugulis 1✒✹✒❏❲❥✹✒✒✹❏❥✒❲✹✒✒❏❥✹❲✒✹✒❏❥✒✹❲✒❏✹✒❥✒❲✹❏✒❥✹✒❲❏✒✹5❥✹❏❲✹❥✺❏✹❲❱✺❥✹❏✺❱❲❥❏✺8❱✺❲❥❏✺❱❲❏❥②❦✺✺❱②❏❥❲❦✺②❏❱✺❥❲❦②✺❏❱❦❲②❏2❱②❦❲❏❱✒②❦✒❲❀❏❲✒②❱✒❀❲✒②❲❀✒1✒②❲❀9❲0②❀✪✪❲✪❲✪❀②✪✪❱✪❲❀✪❲②✪t❦✪✪❱❀✪✪t✪❲❦✪❀✪❱4✪t❀❲❦❱❀t✎❦❲❥✎❀❱t✎❀❦❲❥✎❱t✎❀❦❥✎❲t❱❀✎❥✎t❲❱✎6❥t✎❲❱✎t✎❥❱❲✎④t✎❥④❲✎t❥7④❲t❥④✹t❲④❥✹t✹❲④❥✹t④✹❲❥t✹④❲✹❥t④✹❲❥✹t④✹3 Fig.1. - Γ 4 2.2.2. n=3. Γ has been described in Daugulis [8]. It is cumbersome to depict so that its 8 structure and automorphisms are visible. We give descriptions of its three induced subgraphs Γa, Γb, Γc. 9 ✰ ✠✓✘ ✰ ✠✠✠✠✠✓✠✓✠✓✓✠✓✠✘✓✘✓✘✘✓✘✘✘ ✰✰✰✰✰✰✰✰ ✠ ✓ ✘ ✠ ✘ 8 r▲r▲r▲r▲r▲r▲r▲71✬✬✬✬✠✬✬✠✬✬✠✬✬✠✠✠✠✠✠✠✠✗✗✗✗✗✗✗✗62✗✘✘✘✘✘✘✘✘✘ 53 ▲r▲r▲r▲r▲r▲r▲r4 ✬✬✬✬✬✬✬✬✬ ✗✗✑✗✑✗✗✑✗③✗✑✗✗✑✗③✑✑③✑✑③✑③③③③③③③③③③③ 10 Fig.2. - Γa =Γ8[1,2,..,8,9,10]. Graphswith2n+6verticesandcyclicautomorphismgroupoforder2n 5 11 8✽▲r✈✽▲r✈✽✽▲r✈✽▲r✈✽▲r✈✽✽▲r✈✽▲r✈✽✈✽17✽✈✽✲✈✽✲①✲✈✽✲①✽✲✈✲✽①✲✈✲✽①✲✈✲①✈①✈①✟✈①✟✈✈✟①✈✟✈①✈✟✈✟①✈✈✟26①✈✟✈①✟✈✈✟①✈✟✈①✈✟✈①✟✈✟✈✟✟✈✟✬✬✈✬✟✽✬✬✈✟✬✽✬✟✬✽✬✈✬✟✬✽✬✈✟✬✬✽✬✟✬✈✽✬✬✬53✈✽✽✈✽r✈▲✽r▲✈✽✽r▲✈✽r▲✈✽r▲✈✽✽r▲✈✽r▲✈✽4 12 Fig.3. - Γb =Γ8[1,2,..,8,11,12]. 14 8✈▲r▲r✈✈▲r▲r✈▲r✈▲r✈▲r✈✈17✈✬✲✈✬✬✲✬✬✲✈✬✲✬✬✲✈✬✬✲✬✬✲✈✬✲✬✬✲✈✬✬✲✬✬✈✈✟✈✟①✈✟①✟✈①✟✈✟①✈✟26①✟✈✗①✗✟✑✗✈✑✗✟①✗✑✗✟✗✑✈✗①✑✗✟✗✑✈✗①✟✗✑✗✑✗✟①✗✑✗✟✗✑①✗✗✟①✟✟①✽✟✽①✟✽①✟✽✟①✽✟✽53✽✽✽r▲✽r▲✽✽r▲✽r▲✽r▲✽✽r▲✽r▲✽4 13 Fig.4. - Γc =Γ8[1,2,..,8,13,14]. Aut(Γ )≃Z/8Z and it is generated by the vertex permutation 8 g =(1,2,3,4,5,6,7,8)(9,10,11,12)(13,14). Subgraphs Γ [1,2,..,8,9,11,13]and Γ [1,2,..,8,10,12,14]which can be thought 8 8 asbeingdrawnaboveandbelowtheorbit{1,2,..,8}areinterchangedandrotatedby g. In particular, the permutation g′ =(1,2,3,4,5,6,7,8)(13,14) 6 P.Daugulis is an automorphism of Γc. There are 3 Aut(Γ )-orbits: {1,2,3,4,5,6,7,8},{9,10,11,12},{13,14}. 8 2.3. Automorphism group of Γm. Proposition 2.5. Let n≥2, n∈N, m=2n. Let Γm be as defined above. For any n Aut(Γm)≃Z/mZ. Proof. We will show that Aut(Γm)=hgi where g =(1,2,...,m)(m+1,m+2,m+3,m+4)(m+5,m+6). Since g has order m, this will prove the statement. Step 1: Inclusion hgi≤Aut(Γm). Wehavetoshowthatg mapsanedgeofeachtypetoanedge. Additionofindices involving i∈Vm is meant mod m. 1. The edge of type 1 (i,i+1) is mapped by g to the edge (i+1,i+2). 2. g(m+1)=m+2,if i≡1 or 2(mod 4),then g(i)≡2 or 3(mod4). Any edge of type 2 (m+1,i) is mapped by g to the edge of type 3 (m+2,i+1). 3. g(m+2)=m+3,if i≡2 or 3(mod 4),then g(i)≡3 or 0(mod4). Any edge of type 3 (m+2,i) is mapped by g to the edge of type 4 (m+3,i+1). 4. g(m+3)=m+4,if i≡3 or 0(mod 4),then g(i)≡0 or 1(mod4). Any edge of type 4 (m+3,i) is mapped by g to the edge of type 5 (m+4,i+1). 5. g(m+4)=m+1,if i≡0 or 1(mod 4),then g(i)≡1 or 2(mod4). Any edge of type 5 (m+4,i) is mapped by g to the edge of type 2 (m+1,i+1). 6. g(m+5)=m+6, if i≡1(mod 2), then g(i)≡0(mod 2). Any edge of type 6 (m+5,i) is mapped by g to the edge of type 7 (m+6,i+1). 7. g(m+6)=m+5, if i≡0(mod 2), then g(i)≡1(mod 2). Any edge of type 7 (m+6,i) is mapped by g to the edge of type 6 (m+5,i+1). 8. g changes parity of each of vertices m+1,...,m+6, therefore any edge of type 8 is mapped by g to an edge of type 8. Thus g ∈Aut(Γm) and the inclusion is proved. Step 2: Inclusion Aut(Γm)≤hgi. Let f ∈ Aut(Γm). We will show that f = gα for some unique α(mod m). This Graphswith2n+6verticesandcyclicautomorphismgroupoforder2n 7 will imply that f ∈hgi. There are two subcases: n6=3 and n=3. Foranyn≥2theverticesm+5andm+6aretheonlyverticeshavingeccentricity 3, so they must be permuted by f. Let n 6= 3. Suppose f(1) = k. Since n 6= 3, we have that deg(1) = 5, deg(v) = m +1 6= 5 for any v ∈ O , therefore f(1) ∈ O . Moreover, f permutes both O and 2 2 1 1 O . Consider the f-image of the edge (1,m+5). (f(1),f(m+5)) = (k,f(m+5)) 2 must be an edge, therefore 1. if k ≡1(mod 2), then f(m+5)=m+5, 2. if k ≡0(mod 2), then f(m+5)=m+6. It follows that f|O3 =gk−1. Consider the f-image of Γm[1,2,m+1,m+5], denote its isomorphism type by Γ , see Fig.5. 0 m+5 ▼▼▼▼▼ m+1 1qqqqqq ❍❍❍❍❍2 Fig.5. - Γ0 ≃Γm[1,2,m+1,m+5]. Vertex 2 must be mapped to a Γm[O1]-neighbour of k. For any k ∈O1 there are two triangles containing the vertex k and a vertex adjacent to k in Γm[O1]. Taking into accountthatf(m+5)∈O we cancheckthatthere is only one suitable induced 3 Γm-subgraph containing k, another vertex in O1 adjacent to k and a vertex in O3 which is isomorphic to Γm[1,2,m+1,m+5]: 1. if k ≡1(mod 4), then Γm[k,k+1,m+1,m+5]≃Γ0; 2. if k ≡2(mod 4), then Γm[k,k+1,m+2,m+6]≃Γ0; 3. if k ≡3(mod 4), then Γm[k,k+1,m+3,m+5]≃Γ0; 4. if k ≡0(mod 4), then Γm[k,k+1,m+4,m+6]≃Γ0. (Indices involving k are meant mod m, k ∈Vm). It follows that in each case we must have f(2) ≡ k + 1(mod m). By similar arguments for all j ∈ {1,2,..,m} it is proved that f(j) ≡ (k−1)+j(mod m), thus f|O1 =gk−1. Finally we describe f|O2. It can also be found considering Γm-subgraphs iso- morphic to Γ , but we will use edge inspection. Consider the f-images of the 0 8 P.Daugulis edges (1,m+1) and (1,m+4). Vertex pairs (f(1),f(m+1)) = (k,f(m+1)) and (f(1),f(m+4)) must be edges, therefore we can deduce images of all O vertices. 2 1. if k ≡ 1(mod 4), then f(m+1) = m+1, f(m+3) = m+3, f(m+2) = m+2,f(m+4)=m+4 hence f|O2 =id=g0 =gk−1, 2. ifk ≡2(mod4),thenf(m+1)=m+2,f(m+3)=m+4,f(m+4)=m+1, f(m+2)=m+3 hence f|O2 =g =gk−1, 3. ifk ≡3(mod4),thenf(m+1)=m+3,f(m+3)=m+1,f(m+4)=m+2, f(m+2)=m+4 hence f|O2 =g2 =gk−1, 4. ifk ≡0(mod4),thenf(m+1)=m+4,f(m+3)=m+2,f(m+2)=m+1, f(m+4)=m+3, hence f|O2 =g3 =gk−1, Thus if n6=3 and f(1)=k, then f =gk−1, therefore f ∈hgi. In the special case n = 3 we also consider f-images of Γ [1,2,9,13] and find 8 suitable Γ -subgraphs isomorphic to Γ . It is shown similarly to the above argument 8 0 that f is uniquely determined and f ∈hgi. 2.4. Othergraphs. Otherm+6-vertexgraphswithcyclicautomorphismgroup Z/mZ can be obtained starting from Γm and adding or removing edges in the orbit induced graphs Γm[Oi], complementing orbit subgraphs and edges between orbits. 2.5. Conclusion. For a finite group G the Babai’s construction requires 2|G| vertices for a graph to have automorphismgroup isomorphic to G, two orbits having |G|elementseach. Exceptforsomesmallgroupsandseriessuchassymmetricgroups theexactminimalnumberofverticesforundirected(anddirected)graphsremainsan unsolvedproblem. WehaveshownthatifGiscyclicoforder2n,thenµ(G)≤|G|+6. Somecomputations(notdescribedinthisarticle)indicatethatfor|G|=8thisbound is exact. We note that lim |Vm| =1. n→∞|Aut(Γm)| ThustheBabai’sboundfortheminimalnumberofverticesforundirectedgraphs with a given automorphism group is improved in the case of cyclic 2-groups. This result implies related consequences for finite undirected graphs having abelian auto- morphism groups of order divisible by 2. Acknowledgement. Computationswereperformedusingthecomputationalal- gebra system MAGMA, see Bosma et al. [4], and the program nauty made public by Brendan McKay, available at http://cs.anu.edu.au/bdm/data/, see McKay and Piperno [12]. REFERENCES Graphswith2n+6verticesandcyclicautomorphismgroupoforder2n 9 [1] W.C.Arlinghaus(1985), Theclassificationofminimalgraphswithgivenabelianautomorphism group. Memoirs of the American Mathematical Society, v.57, Providence, Rhode Island, USA. [2] L. Babai (1974), On the minimum order of graphs with given group, Canad. Math. Bull., 17, pp.467-470. [3] L. Babai (1995), Automorphism groups, isomorphism, reconstruction, In Graham, Ronald L.; Grotschel, Martin; Lovasz, Laszlo, Handbook of Combinatorics I, North-Holland, pp. 1447-1540. [4] W.Bosma,J.Cannon,andC.Playoust(1997),TheMagmaalgebrasystem.I.Theuserlanguage, J.SymbolicComput.,24,pp.235-265. [5] I.Z.Bouwer,R.Frucht(1973), Line-minimalgraphswithcyclicgroup, InJagdishN.Srivastava, Asurveyofcombinatorialtheory,North-Holland,pp.53-69. [6] P. Cameron (2004) Automorphisms of graphs, in Topics in Algebraic Graph Theory (ed. L. W. Beineke and R. J. Wilson), Cambridge Univ. Press, Cambridge, (ISBN 0521801974), pp.137-155. [7] P. Daugulis (2014) 10-vertex graphs with cyclic automorphism group of order 4. http://arxiv.org/abs/1410.1163. [8] P. Daugulis (2015) 14-vertex graphs with cyclic automorphism group of order 8. http://arxiv.org/abs/1501.04066. [9] R. Diestel (2010), Graph Theory. Graduate Texts in Mathematics, Vol.173, Springer-Verlag, Heidelberg. [10] R. Frucht (1939), Herstellung von Graphen mitvorgegebener abstrakter Gruppe, Compositio Mathematica(inGerman)6,pp.239250, Harary,Frank,GraphTheory(1969), AddisonWesley,Reading,MA. [11] F.Harary(1969), GraphTheory, Addison-Wesley,Reading,MA. [12] B.D.McKayandA.Piperno(2013), PracticalGraphIsomorphism,II, J.SymbolicComputa- tion,60,pp.94-112.