ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 8 (2015) 381-408 Quartic integral Cayley graphs* Marsha Minchenko, Ian M. Wanless School of Mathematical Sciences, Monash University, Vic, 3800, Australia Received 19 June 2013, accepted 11 February 2015, published online 5 June 2015 We give exhaustive lists of connected 4-regular integral Cayley graphs and connected 4-regular integral arc-transitive graphs. An integral graph is a graph for which all eigenvalues are integers. A Cayley graph Cay(r, S) for a given group r and connection set S c r is the graph with vertex set r and with a connected to b if and only if ba-1 G S. Up to isomorphism, we find that there are 32 connected quartic integral Cayley graphs, 17 of which are bipartite. Many of these can be realized in a number of different ways by using non-isomorphic choices for r and/or different choices for S. A graph is arc-transitive if its automorphism group acts transitively on the ordered pairs of adjacent vertices. Up to isomorphism, there are 27 quartic integral graphs that are arc-transitive. Of these 27 graphs, 16 are bipartite and 16 are Cayley graphs. By taking quotients of our Cayley or arc-transitive graphs we also find a number of other quartic integral graphs. Overall, we find 9 new spectra that can be realised by bipartite quartic integral graphs. Keywords: Graph spectrum, integral graph, Cayley graph, arc-transitive, vertex-transitive bipartite double cover, voltage assignment, graph homomorphism. Math. Subj. Class.: 05C50, 05C25 1 Introduction We give exhaustive lists of connected 4-regular integral Cayley graphs and connected 4-regular integral arc-transitive graphs. For reasons which will become apparent, we first restrict our attention to the bipartite case. An integral graph is a graph for which all eigenvalues of the adjacency matrix are integers. The spectrum of a graph is the eigenvalues with their multiplicity. Bipartite graphs have eigenvalues that are symmetric with respect to 0 and r-regular graphs have largest eigenvalue r with multiplicity equal to the number of connected components. For * Research supported by ARC grant DP120100197. E-mail addresses: marsha.minchenko@monash.edu (Marsha Minchenko), ian.wanless@monash.edu (Ian M. Wanless) Abstract ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 378 Ars Math. Contemp. 8 (2015) 365-382 details we refer to [10]. Therefore for connected 4-regular bipartite integral graphs, the spectrum has the form {4, 3x, 2y, 1z, 02w, -1z, -2y, -3x, -4}; which we abbreviate by simply specifying the quadruple [x, y, z, w]. There are only finitely many connected 4-regular bipartite integral graphs. Cvetkovic [6] proved that the diameter D of a connected graph satisfies D < s - 1, where s is the number of distinct eigenvalues. For connected r-regular integral graphs, it follows that R < D < 2r where R is the radius of the graph. Cvetkovic et al. [7] showed that the number of vertices in a connected r-regular bipartite graph is bounded above by (2(r - 1)R - 2)/ (r - 2) if r > 3. Therefore, connected 4-regular bipartite integral graphs have at most 6560 vertices. All graphs in this paper are simple, undirected, and have n vertices. Since a 4-regular graph is integral if and only if each of its components is integral, from this point on we will assume that all graphs are connected. We use the acronym QIG as shorthand for a connected quartic integral graph. Cvetkovic et al. [7] found quadruples [x, y, z, w] that are candidates for the spectrum of a bipartite QIG. They called these possible spectra. Research activities regarding the set of possible spectra fall into two streams: eliminate possible spectra based on new information and/or techniques, or find graphs that realize a possible spectrum. Useful tools include an identity by Hoffman [11] and equations relating the spectral moments to the closed walks of length I < 6. All QIGs that avoid eigenvalues of ±3 and realize a possible spectrum are found in [24]. Stevanovic [23] eliminates spectra using equations arising from graph angles. In the same paper he determines that the possible values for n are between 8 and 1260, except for 5 identified spectra. Stevanovic et al. [25] extend the equations for the ^-th spectral moment to an inequality for I = 8. They make use of a correspondence between closed walks in an r-regular graph and walks in an infinite r-regular tree and find recurrence relations for the number of closed walks. The upper bound for n is improved to give 8 < n < 560. Equations for I > 8 are found in [16] by counting a certain type of closed walk in terms of the counts of small subgraphs of the graph. All of the bipartite QIGs with n < 24 that realize one of the possible spectra were found and are listed with drawings in [25]. We give 12 new graphs that realize possible spectra from the set given in [25]. Of these graphs, 3 are co-spectral to an integral graph listed in [7]. Their spectra are [4,6,4, 5] and [6,16,10,3], and [9,16,19,0]. The spectra not previously known to be realized by a graph are [3,4,1, 6], [3, 5, 9,0], [5,4,7,4], [6,12, 2, 9], [8,10,16,1], [10,14,18, 2], [12, 28, 4,15], [22, 28, 34, 5], and [27, 28,49,0]. Of the 12 graphs, 3 appear in the census of Potocnik et al. [17, 18] but were not recognized as integral. We also list 49 new non-bipartite QIGs that, to our knowledge, do not appear anywhere in the literature. Of these graphs, only 3 appear in the census of Potocnik et al. [17, 18] but were not tested for integrality. A Cayley graph Cay(r, S) for a group r and connection set S C r is the graph with vertex set r and with a connected to b if and only if ba-1 G S. Let Zt, Dt, and Qt denote the cyclic, dihedral, and quaternion groups of order t respectively, and St, At the symmetric and alternating groups of degree t. Klotz and Sander [12] showed that if every Cayley graph Cay(r, S) over a finite Abelian group r is integral then r G {Z2, Z3, Z|, Z2 x Z3, Z2 x Z4}, where s > 1, t > 1. The analogous result for non-Abelian r was determined independently by Abdol-lahi and Jazaeri [1] and Ahmady et al. [4]: if every Cayley graph Cay(r, S) over a finite non-Abelian group r is integral then r G {S3, Z3 x Z4, Q8 x Z2}, where r > 0. M. Minchenko and I. M. Wanless: Quartic integral Cayley graphs 383 Estelyi and Kovacs [8] considered the groups for which all Cayley graphs Cay(T, S) over a group r are integral if |S| < k. The authors proved that for k > 6, r consists only of the groups above: {Z|, Z3, Z4, Z2 x Z3, Z2 x Z4} U {S3, Z3 x Z4, Q8 x Z2}, s > 1, t > 1, r > 0. Moreover, for k G {4,5} there is only one extra possibility, namely that r is the generalised dicyclic group with Z3q x Z6 as a subgroup of index 2, where q > 1. Abdollahi and Vatandoost [2] showed that there are exactly 7 connected cubic integral Cayley graphs. They found that Cay(T, S) is integral for some S with |S| =3 if and only if r is isomorphic to Z2 x Z2, Z4, Z6, S3, Zf, Z2 x Z4, D8, Z2 x Z6, Di2, A4, S4, D8 x Z3, D6 x Z4 or A4 x Z2. A set of possible orders for Cayley QIGs on finite Abelian groups have been determined by Abdollahi et al. [3]. They showed that for an Abelian group, r, if Cay(T, S) is a Cayley QIG then |r| G {5, 6, 8, 9,10,12,16,18, 20, 24, 25, 32, 36, 40, 48, 50, 60, 64, 72, 80, 96,100,120,144}, but they did not establish whether Cayley QIGs of these orders exist. We find that the precise set of orders of Cayley QIGs on Abelian groups is {5, 6,8,9,10,12,16,18,24,36}. More generally, we consider all groups and find that many Cayley QIGs are on non-Abelian groups. Thus, we show that for any group r, if Cay(T, S) is a Cayley QIG then |r| G {5, 6, 8, 9,10,12,16,18, 20, 24, 30, 32, 36,40,48, 60, 72,120}. Furthermore, for each of these orders Cayley QIGs exist. For a given Cayley graph G, there may exist many different pairs (T, S) of groups r and connection sets S such that G = Cay(T, S). We call isomorphic Cayley graphs on the same group r equivalent if their connection sets are from the same orbit of the automorphism group of r (see for example [13]): Definition 1.1. Let r be a group and Aut(r) be the automorphism group of r. If Cayley graph Cay(r, S) = Cay(r, T) and Sff = T for some a G Aut(r) then Cay(r, S) and Cay(r, T) are equivalent. Any other connection sets give non-equivalent Cayley Graphs. Cayley graphs from different groups are non-equivalent. There are, up to isomorphism, only 32 connected quartic integral Cayley graphs; but each graph is realized in up to 18 non-equivalent ways. Of the 32 graphs, 17 are bipartite. A graph is arc-transitive if its automorphism group acts transitively on the ordered pairs of adjacent vertices. There are, up to isomorphism, only 27 connected quartic integral graphs that are arc-transitive. Of the 27 graphs, 16 are bipartite, 5 of which are not Cayley graphs. In Section 2 we find that most of the feasible spectra from [25] cannot be realized by vertex-transitive QIGs. Section 3 summarises the algorithm used for finding all of the bipartite Cayley QIGs. Section 4 gives our main results. It includes tables giving the details of the Cayley QIGs and the bipartite arc-transitive QIGs, some drawings, and some non-bipartite QIGs that result from finding quotients of our bipartite graphs. 2 Vertex-transitive quartic integral graphs A graph is vertex-transitive if its automorphism group acts transitively on its vertices. In this section, our aim is to compile a set S that includes all possible spectra that might be 378 Ars Math. Contemp. 8 (2015) 365-384 realized by a vertex-transitive QIG, but is otherwise as small as we can make it. Initially we take S to be all possible spectra from [25], and candidates will be progressively removed from the set as we work through this section. We will need some notation for (unlabelled) subgraphs. We let Ci denote the ¿-cycle, Cil.i2...ih denote j-cycles sharing a single vertex for j = 1,..., h, Cil-i2 an i1-cycle joined to an i2-cycle by an edge, and ©il,i2,...,ih two vertices joined by internally disjoint paths of lengths j for j = 1,..., h. Examples of this notation for subgraphs appear in Figure 1. (a) C4.3.3 (b) C4-3 (c) ©2,2,1 Figure 1: Subgraph notation If at any point we encounter subgraphs that cannot be described by our notation, we draw a picture of the subgraph like those in Figure 1. For any graph H, let [H] denote the number of subgraphs of G that are isomorphic to H, where the parent graph G will be implicitly specified by the context. In [7], Equations (2.1) and (2.2) are used to determine [C4] and [C6] for a given [x, y, z, w]. 2(44 + 34x + 24y + z) = 28n + 8[C4], (2.1) 2(46 + 36x + 26y + z) = 232n + 144[C4] + 12[C6]. (2.2) In [16], these equations were extended to higher spectral moments of general regular graphs. By specialising to 4-regular bipartite graphs, we obtain the following equations: 2(48 + 38x + 28y + z) = 2092n + 2024[C4] + 288[C6] + 16[C8] + 32[C4.4] + 96[©2,2,2,2] + 48[©2,2,2] + 16[©3,3,i], 2(410 + 310x + 210y + z) = 19864n + 26160[C4] + 4860[C6] + 480[C8] + 20[C10 ] + 960[C4-4] + 40[C4_4] + 40[C6-4] + 1440[©2,2,2 ] + 520[©3,3,1] + 2880[©2,2,2,2] + 40[©4,2,2] + 20[©5,3,1] + 120[©3,3,3,1] + 120[©4,2,2,2 ] + 120[^>] + 80^ ¡]. (2.3) The girth of a graph is the length of the shortest cycle contained in the graph. We use Equations (2.3) to determine the girth where [C4] = [C6] =0 for a given [x, y, z, w] and also to determine the values for [C8] and [C10] where possible. Vertex-transitive graphs have the same number of ¿-cycles incident with each vertex, so the number of vertices divides ¿[Ci]. We apply this observation for i e {4,6,8,10} to the possible spectra for which the value of [Ci] can be deduced. We eliminate those quadruples that cannot be realized by a vertex-transitive QIG from S. M. Minchenko and I. M. Wanless: Quartic integral Cayley graphs 385 For example, if we consider [5, 6,11,1] with n = 48, [—4] = 24, and [—6] = 140 then 4[—4] 4(24) _ , 6[—6] 6(140) 35 _ 4—1 = = 2 e N but = ^ = 35 £ N, n 48 n 48 2 where N denotes the set of non-negative integers. Thus [5,6,11,1] is eliminated from S. In contrast, for [12,12, 20, 3] with n = 96, [-4] = 24, [-6] = 128, and [-8] = 528. We are able to find [-8] from (2.3) by deducing that [-4-4] = [©2,2,2,2] = [©2,2,2] = [©3,3,1] = 0 because there is only one 4-cycle incident with each vertex. In fact, 4[—4] 4(24) 6[—6] 6(128) 8[-8] 8(528) --1 = = 1 e N, ^ = ) =8 e N, and = - =44 e N. n 96 n 96 n 96 In this case, [—10] cannot be determined from (2.3), so we consider it unknown. Thus [12,12,20,3] remains in S. It is also plausible to eliminate quadruples from S using arguments specific to particular cases. We give one example to demonstrate the possibility. Consider [24, 4, 40, 3] with [—4] = 72 and [—6] = 0. There are 4(72)/144 = 2 copies of —4 incident at each vertex. Since [—6] = 0, we know [©3,3,1] = 0. Also, with only two 4-cycles at each vertex, [©2,2,2,2] = [©2,2,2] = 0. Since two 4-cycles meet at exactly one vertex of a —4.4, [—4.4] = 144. From Equation (2.3) we get that, 2(48 + 38(24) + 28(4) + 40) = 2092(144) + 2024(72) + 16[—8] + 32(144), which gives the contradiction [—8] = -216. Thus we remove [24,4,40,3] from S. This entry is underlined in Table 1. We eliminate two quadruples from S using the following Lemma [5, Prop. 16.6]: Lemma 2.1. Let G be a vertex-transitive graph which has degree r and an even number of vertices. If A is a simple eigenvalue of G, then A is one of the integers 2a — r for 0 < a < r. The orders associated with the eliminated quadruples are 36 and 72. Both entries have 1 as a simple eigenvalue. These entries are underlined and highlighted in bold in Table 1. Using the above methods, we reduced the set S from the initial 828 possible spectra to 59 quadruples in the final version. Henceforth S will refer to this final set of 59 quadruples (see Appendix A). 386 Ars Math. Contemp. 8(2015)381-408 n Girth n Girth n Girth n Girth 8 4 36 4,4,4, q7 96 4,q27,h3 240 6,8,q30,h2 10 4 40 4,q10 112 q34,h2 252 q28,h3 12 4,4 42 4,q14 120 4,4,4,6,6,q28 280 8,q23,h2 14 q1 48 4,q12,h2 126 4,6,q38,h1 288 6,q21,h1 16 4,qx 56 q16,h2 140 q40,h2 336 q14,h2 18 4,q1 60 4,4,4,4,6,q15 144 4,4,6, q31,^1 360 6,6,8,q11 20 4,q3 70 6,q23 160 q33,h2 420 8,q5,h1 24 4,4,4,q3 72 4,4,4,4,6,q18 168 6,q35,h2 480 8,q2 28 q8 80 q22,h2 180 4,6,6,6,q38 504 h1 30 4,4,6,q6 84 q23,h7 210 6,q35,h2 560 10 32 6,q8 90 4,4,6,6,q27 224 q32,h3 Table 1: Finding the set S Table 1 summarizes the process of finding S. For every order, we consider each [x, y, z, w] and check whether we get integer counts at each vertex for each Q where [Q] is known and i e {4, 6,8,10}. A 'qj' in the table denotes that for the given n there were j possible spectra eliminated because 4[C4]/n e N. An ' in the table denotes that for the given n there were j possible spectra which satisfied 4[C4]/n e N that were eliminated because 6[C6]/n e N. If i[Cj]/n e N for all i where [Q] is known for a possible spectra, then the girth is recorded. Thus an entry of 4,4,6,q6 indicates that there are three possible spectra in S associated with that order. If those quadruples are all realized by graphs (where a graph in this case may actually be a set of cospectral graphs) then two graphs will have girth 4 and the other will have girth 6. It also indicates that 6 possible spectra with 4[C4]/n e N were eliminated because 6[C6]/n e N. 3 The algorithm In this section we outline our method for finding bipartite Cayley QIGs, using the set S compiled in Section 2. Define Q to be the set of orders associated with the spectra in S. Cayley graphs are vertex-transitive, so we only consider groups r of order n e Q. To reduce the number of groups to be considered, we use a result similar to one in [18]. Let r' denote the commutator subgroup of a group r. Lemma 3.1. Let r be a finite group and let Cay(T, S) be a connected Cayley graph of degree at most 4. Then r/r' is isomorphic to one of Z2 x Z2 x Z2 x Z2; Z2 x Z2 x Za with a > 2; Za x Zb with a, b > 2; or Za with a > 1. Proof. Since Cay(T, S) is connected and has degree at most 4, r is generated by an inverse-closed set of at most 4 elements. This must also be true of the quotient group r/r'. Now since r/r' is Abelian, the result follows. □ M. Minchenko and I. M. Wanless: Quartic integral Cayley graphs 387 By Lemma 3.1, we need only consider groups r with r/r' isomorphic to one of Z2 x Z2 x Z2 x Z2, Z2 x Z2 x Za, Za x Zb, or Za. We denote the set of groups that satisfy this property by To construct connected simple undirected 4-regular Cayley graphs Cay(T, S), we considered inverse-closed sets S of four non-identity elements of r that generate r. The search was pruned by placing additional restrictions on S. Let g denote the girth of the graph Cay(r,S). • Since Cay(r, S) is bipartite, the order of s is even for each s G S. • If si, s2 G S and si = s-1, then the order of sis2 is at least g/2 (in particular non-involutions have order no smaller than the girth). • For any set of connection sets that result in equivalent Cayley graphs (in the sense of Definition 1.1), only one representative is chosen. We note that the minimum girth possible for Cay(r, S) is given by Table 1. We summarize the results of our computations in Table 2. The values for n G Q appear as the first column and in the second column the number of groups of order n is given. (We reiterate that Q does not include orders eliminated by the vertex-transitive tests of Section 2). The number of groups in $ of order n are listed in column three. Column 4 contains the number of connection sets S among the groups counted by column 3, subject to the restrictions on S given above. The graphs Cay(r, S) that are bipartite are counted in column 5. The number of isomorphism classes of these graphs appears in column 6. The number of isomorphism classes of integral graphs is recorded in column 7. The last column gives the number of isomorphism classes of arc-transitive integral graphs. A '-' indicates that there are no integral graphs to consider. n #Groups #r e $ #Sets #Bipartite #Isomorphism #Integral #Arc- r S Cay(r,S) Classes Transitive 8 5 5 13 7 1 1 1 10 2 2 2 2 1 1 1 12 5 5 19 11 3 2 1 16 14 14 66 44 5 1 1 18 5 5 12 12 5 1 1 20 5 5 34 20 8 0 24 15 15 151 98 23 3 1 30 4 4 31 31 17 1 1 32 51 48 58 51 16 1 1 36 14 14 149 105 48 1 1 40 14 14 201 146 54 1 0 42 6 6 55 55 36 0 - 48 52 51 840 616 177 1 0 60 13 13 385 281 161 0 - 70 4 4 96 96 73 0 - 72 50 49 1014 765 338 2 1 378 Ars Math. Contemp. 8 (2015) 365-388 90 10 10 236 236 175 0 - 96 231 218 4434 3545 1292 0 - 120 47 47 2833 1968 1123 1 1 126 16 16 427 427 346 0 - 144 197 190 6563 5350 2722 0 - 168 57 57 2388 2212 1601 0 - 180 37 37 2927 2497 1883 0 - 210 12 12 1172 1172 1017 0 - 240 208 205 10884 9885 6791 0 - 280 40 40 4080 3929 3223 0 - 288 1045 968 26391 24815 15695 0 - 360 162 160 15928 14703 11524 0 - 420 41 41 10558 10204 9271 0 - 480 1213 1148 68179 63804 48322 0 - 560 180 177 21764 21433 18704 0 - Table 2: Results at each algorithm step 4 Quartic integral graphs In this section we present the graphs that our computations discovered, starting with the bipartite Cayley case. 4.1 Bipartite Cayley integral graphs As a result of the computation described in Section 3, we have: Theorem 4.1. There are precisely 17 isomorphism classes of connected 4-regular bipartite integral Cayley graphs, as detailed in Table 3. For each bipartite Cayley QIG in Table 3 we give n and the spectrum [x,y, z,w]. Graphs appearing in the paper by Cvetkovic et al. [7] are labelled In,index as in that paper. If the graph is in the census of Potocnik et al. [17, 18] then we give the index in their notation: AT4Val[n][index]. In two columns, we give the groups and connection sets that give rise to each Cayley graph. The first column contains the group, r, with a presentation of that group. We stick as close as possible to the convention of using generators in {a, b, c, d, e} for cyclic groups, {s, t, u, v} for symmetric or alternating groups, and {r, f} for the quaternion group, the dihedral group, or the quasidihedral group. The last column contains the number of involutions in the connection set, S, followed by the connection set itself in terms of the generators from the previous column. M. Minchenko and I. M. Wanless: Quartic integral Cayley graphs 389 Group Connection Sets (#involutions S) Gl : n = S [O, O, O, S] I8,l AT4Val[8][1] Z8 < a I a8 > O {a,a3,a5,a7} Z4 x Z2 < a I a4 > x < b I b2 > 2 {a,b,a3,a2b} O {a, ab, a3, a3b} D8 < r, f I r4, f2, (rf)2 > 4 {f, fr, fr2, rf } 2 {f, r, f r2, f rf } Q8 < r, f I r4, f4,r2f2,rfrf 1 > O {r, f, r3, r2f} Z2 x Z2 x Z2 < a I a2 > x < b I b2 > x < c I c2 > 4 {a, b, c, abc} G2 : n = 1O [O, O, 4, O] Il0,l AT4Val[1O][2] D10 < r, f I r4, f2, (rf)2 > 4 {f, fr, fr2, r2f } Z10 < a I a10 > O {a,a3,a7,a9} G3 : n = 12 [O, 2, O, S] Il2,4 AT4Val[12][2] Z3 x Z4 < a,b I a3, b4, abab-1 > O {b,b3,ba,b3a} Z12 < a I a12 > O {a,a5,a7,a11} D12 < r, f I r6, f2, (rf)2 > 2 {r2f, f, r5, r} 4 {r4f, rf, r2f, r5f } Z6 x Z2 < a I a6 > x < b I b2 > O {a5,a2b,a,a4b} G4 : n = 12 [0,1, 4, O] Il2,2 D12 < r, f I r6, f2, (rf)2 > 2 {rf,r3,r,r5} 4 {rf, r3, r5f, r3f } 4 {rf, r4f, r5f, r3f} Z6 x Z2 < a I a6 > x < b I b2 > 2 {a3,b,a5,a} 378 Ars Math. Contemp. 8 (2015) 365-390 G5 : n = 16 [O, 4, O, S] Iia,i AT4Val[16][1] Z4 X Z4 K a j a4 > X Kb j b4 > O {a,b,a3,b3} (Z4 X Z2) x Z2 K a,b,c j a4,b2 ,c2, aba~1b~1, (aac)2, (bc)2, baca-1c > 2 {ac, a2bc, a3bc, a2c} 2 {bc, a3b, a2c, ab} O {a, a3c,a3,abc} Z4 X Z4 Ka,b j a4,b4,aba-1b > O {a,a3ba,a3,b} Z8 X Z2 K a,b j a8,b2,aba3b > O {a,ab,a3b,a7} QD16 Kr,f j r8,f2, rfr5 f > 2 {r, r4 f, r6 f, r7} Z4 X Z2 X Z2 K a j a4 > X Kb j b2 > X K c j c2 > 2 {a,b,c,a3} Z2 X D8 K a j a2 > X Kr,f j r4, f2, (rf )2 > 4 {a, f, r3f, r2 f} 4 {f, r3f, af, rf } 4 {f, r3f, af, arf } 2 {a, r, f, r3 } 2 {a, r, af, r3} Z2 X Z2 X Z2 X Z2 K a j a2 > X Kb j b2 > X K c j c2 > X K d j d2 > 4 {a, b, c, d} Ga : n = 18 [O, 4, 4, O] Ii8,i AT4Val[18][2] Z3 X S3 K a j a3 > X K s, t j s2, t3, (st)2 > 2 {s, st, ats, a2ts} O {sa, sa2, sat, sa2t} (Z3 X Z3) X Z2 K a, b, c j a3,b3 ,c2, aba-1b-1, (ac)2, (bc)2 > 4 {c, ca, cb, cab} Z6 X Z3 K a j a6 > X Kb j b3 > O {a, a5, a3b, a3b2} Gr : n = 24 [O, 8, O, S] I24,2 AT4Val[24][1] Z4 X S3 K a j a4 > X K s, t j s2, t3, (st)2 > 2 {s, st, at, a3sts} (Z6 X Z2) X Z2 K a, b, c j a6 ,b2 ,c2, aba-1b-1, (aac)2, a3(cb)2 > 2 {a3c, a2c, ab, a5b} Z3 X D8 K a j a3 > X K r, f j r4, f2, (rf )2 > O {ar3 f, a2r3 f, ar3,a2r} S4 K s,t j s2,t3,(st)4 > 4 {st2sts,t2st,stst2s,tst2} O {ts,st2,ststs, tst} 2 {st2sts,tst2,ts,st2} M. Minchenko and I. M. Wanless: Quartic integral Cayley graphs 391 Z2 X A4 Ka j a2 > X K s, t j s2, t3, (st)3 > O {ast, astst, asts, atst} Z2 X Z2 X S3 Ka j a2 > X Kb j b2 > X K s,t j s2,t3, (st)2 > 4 {s, bs, st, ast} Gs : n = 24 [2, 2, 6,1] 124,3 Z4 X S3 K a j a4 > X K s, t j s2, t3, (st)2 > 2 {a,a3,s,st} 2 {s, st, ats, a3ts} D24 K r, f j r12, f2, (rf )2 > 4 {f, rf, r5 f, r6 f } 2 {f, r3 ,r9, rsf } Z2 X (Z3 X Z4) K a j a2 > X K b,c j b3,c4, bcbc-1 > O {c,c3,ab,ac3bc} (Za X Z2) X Z2 Ka,b,c j a3 ,b2 ,c2 ,aba-1b-1, (ac)2, (bc)4 > 4 {c, b, ca, cbc} 2 {c, bcb, ba, bcac} 2 {c, ca, cbcac, bac} O {cb, bc, ba, bcac} Z12 X Z2 K a j a12 > X Kb j b2 > O {a3,a9,a4b,asb} Z3 X Ds K a j a3 > X K r, f j r4, f2, (rf )2 > 2 {r3f, rf, a2 f, af } O {r, r3,ar3f, a2r3f } Z2 X Z2 X S3 K a j a2 > X Kb j b2 > X K s,t j s2,t3, (st)2 > 4 {s, b, a, st} 4 {s, b, st, ats} 4 {s, sb, ast, ats} 2 {s, b, at, asts} 2 {s, sb, at, asts} Za X Z2 X Z2 K a j a6 > X Kb j b2 > X K c j c2 > 2 {a3,b, a2c, a4c} G9 : n = 24 [S, O, 5, S] I24,4 S4 K s, t j s2,t3,(st)4 > 4 {s,t2st, st2sts, stst2st} Z2 X A4 K a j a2 > X K s, t j s2, t3, (st)3 > 2 {a, as, at2s, ast} G10 : n = SO [0,1O, 4, O] I3o,i AT4Val[3O][4] Z5 X S3 K a j a5 > X K s, t j s2, t3, (st)2 > O {as, a2st, a4s, a3st} D30 K r, f j r15, f2, (rf )2 > 4 {f, r2 f, r3f, r11 f } 392 Ars Math. Contemp. S (2G15) 3S1-4GS Gii : n = 32 [0,12, 0, 3] Is2,i AT4Val[32][4] Zs x Z4 O {a, a7, ab, a3b3} (Zs x Z2) x Z2 < a,b,c I as,b2 ,c2 ,a2ba6b, (aac)2, (bc)2 ,ba-1cac > 2 {a4c, a2c, a7bc, a5c} Z2.((Z4 x Z2) X Z2) = (Z2 x Z2).(Z4 x Z2) O {ba,a3b,a3,a5} (Z4 x Z4) X Z2 Z4.DS = Z4.(Z4 x Z2) O {a, a7 ,a7ba, a4b} (Z4 x Z4) X Z2 < a,b,c I a4,b4,c2,aba-1b-1, (ac)2, (bc)2 > 4 {c, cb, ca, abc} (Zs x Z2) x Z2 < a,b,c I as,b2 ,c2, aba-1b, aca-1c, a4bcbc, (bc)4 > 2 {b, c, abc, a3bc} Z2 x QD16 < a I a2 > x < r,f I rs, f 2,rfr5 f > 2 {ar, r3,r5, r2f } (Zs x Z2) x Z2 < a, b, c I as,b2 ,c2, aba-1b-1, (ac)2, a4(bc)2 > 4 {a7c, a2c, ac, a4b} (Z2 x Ds) x Z2 < a,r,f,b I a2 ,r4, f2 ,b2, aba-1b-1 ,r(fa)2, r2(bf )2 > 4 {r2f,ar2,rf,rab} (Z2 x Qs) x Z2 2 {r2b, a, ar3fb, ar3b} < a,r,f,b I a2,r4,f4,b2,ara-1r-1,afa-1f-1,r2f2,rfrf-1, (rrb)2 ,r2 (ab)2 ,brbr-1 f > (Z2 x Qs) x Z2 4 {b, a, br, brf} < a,r,f,b I a2,r4,f4,b2,ara-1r-1,afa-1f-1,r2f2,rfrf-1, (rb)2, fbf-1b-1,arbar-1b > G12 : n = 36 [4, 4, 4, 5] Is6,3 AT4Val[36][3] Z3 x (Z3 X Z4) < a I a3 > x < b,c I b3,c4,bcbc-1 > O {ac, a2c3,a2cb,ac3b} (Z3 x Z3) X Z4 < a,b,c I a3 ,b3, c4 ,aba-1b-1, (acc)2 ,acac-1b-1 > O {a2b2c3,b2c,a2bc3,ac} S3 x S3 < s, t I s2, t3, (st)2 > x 4 {u, s, uv, st} 4 {u, uv, svu, stvu} 2 {su, stu, tsv, tsuvu} O {tu, stsu, sv, suvu} M. Minchenko and I. M. Wanless: Quartic integral Cayley graphs 393 Z6 x S3 < a I a6 > x < s, t I s2, t3, (st)2 > 2 { a, a5 , a3 s, a3 st} 2 {a3s,a3st,a2ts,a4ts} O {as, a3t, a5s, a3sts} Z2 x ((Z3 x Z3) x Z2) x < b,c,d I b3,c3,d2,bcb-1c-1, (bd)2, (cd) 4 {d, dc, adb, adcdbd} 2 > 2 {d, dc, ab, adbd} Za x Za < a I a6 > x < b I b6 > O {a,a5,b,b5} Gis : n = 40 [4, 6, 4, 5] Z2 x (Z5 x Z4) x 2 {ac2 ,ac2b,c,c3} Gi4 : n = 48 [6, 4,10, S] I48,i Z2 x Z4 x S3 < a I a2 > x < b I b4 > x < s, t I s2, t3, (st)2 > 2 {s,a,bt,b3sts} Ds x S3 x < s, t I s2, t3, (st)2 > 4 {s, rfs, fts, r2 fst} 4 {rf, rfs, fts, r2 fst} 2 {s, rfs, r3t, rsts} 2 {rf, rfs, r3t, rsts} Z2 x ((Za x Z2) x Z2) < a I a2 > x < b, c, d b6 ,c2 ,d2 ,bcb-1c-1, (bbd)2, b3 (dc)2 > 4 {a, c, b4d,b3d} I Za x Ds < a I a6 > x 2 {a3 ,a3r3 f, ar, a5r3} Z2 x S4 < a I a2 > x < s, t I s2, t3, (st)4 > 4 {a, s, stst2s, st2sts} 4 {as, at2st, atst2, stst2st} 2 {s,astst2, atst2s, atst2st} Z2 x Z2 x A4 < a I a2 > x < b I b2 > x < s, t I s2, t3, (st)3 > 2 {a,abtst2 ,abtst,abt2st2} Z2 x Z2 x Z2 x S3 < a I a2 > x < b I b2 > x < c I c2 > x < s s2,t3,(st)2 > 4 {s, b, cst, ats} ,t I G15 : n = 72 [6,16,10, S] AT4Val[72][12] Z3 x S4 < a I a3 > x < s, t I s2, t3, (st)4 > O {ast, a2tst, a212s, aststs} (Z3 x A4) x Z2 4 {atb, ab, tsbt, tbs} < a, s, t, b I a3, s2,t3,b2,asa-1s-1 ,ata-1t-1, stbsbt-1, (ab)2, (tb)2,(st)3 > A4 x S3 O {tu, t2u,tsuv, st2uv} < s, t I s2 ,t3, (st)3 > x 378 Ars Math. Contemp. 8 (2015) 365-394 Za x A4 K a j a6 > x K s, t j s2, t3, (st)3 > O {ast,a3t,a3t2,a5stst} Gis : n = 72 [S, 10,16,1] (Z3 x (Z3 X Z4)) X Z2 K a,b,c,d j a3 ,b3, c4, d2, aba-1b-1, aca-1 c-1, bdb-1d-1, adad-1 ,bcbc-1 ,c2d2 > 2 { dc, dacb, ad, d2 ad} (Za x S3) X Z2 K a, b, c, d j a2,b4,c3, d3, (ab-1)2,acac-1, (ad)2, cbcb-1, bdb-1d-1,cdc-1d-1 > 4 {a,ab2, abd, abacda} 2 {ab, abcd, cb, b2cb} Za x (Z3 x Z4) K a j a6 > x K b,c j b3,c4,bcbc-1 > O {ab2,a5b,a3b2c,a3b2c3} Z3 x ((Za x Z2) x Z2) K a j a3 > x K b,c,d j b6, c2,d2,bcb-1c-1, (bbd)2,b3(dc)2 > 2 {b5d, b2d, a2b4c,ab2c} O {b2cd,b5cd,a2b4c, ab2c} (S3 x S3 ) X Z2 K s, t, u, v, a j s2, t3,u2,v3,a2,tvt-1v-1, (uv)2, (av)2, svst-1, asasu > 4 {a, sastsat, s, sast} 2 {sas, stsa,atsa,asat2} 2 {asa, atsat2, sastst, asastsat} O {sa, as, atsat, asastst2 } Z2 x ((Z3 x Z3) X Z4) K a j a2 > x K b,c,d j b3,c3,d4,bcb-1c-1, (bdd)2, bdbd-1 c-1 > 2 {ad2, ab2c2d2, ab2d3, ab2cd} O {ab2cd, ab2d3, abc2, ab2c} Z2 x S3 x S3 K a j a2 > x K s, t j s2, t3, (st)2 > x Ku,v j u2 ,v3, (uv)2 > 4 {u, s, auvst, atsvu} 4 {u, au, suv, stvu} 2 {u, s, atv, astsuvu} Z2 x Za x S3 K a j a2 > x Kb j b6 > x K s,t j s2,t3, (st)2 > 2 {ts,ab3ts,bsts,b5t} Gi7 : n = 120 [12, 28, 4,15] AT4Val[120][4] S5 K s,t j s2,t5,(st)4,(st2st3)2 > O {t2st3, tst2st2st, st2stst, tst4} 4 {t(st)2tst4, st2(st)2t,(t2s)2ts, (st2)2st} Z2 x A5 Ka j a2 > x K s,t j s2,t3, (st)5 > 2 {a(tst2s)2t,ast(ts)2 ,ast2(st)2, a(st)3ts} S3 x (Z5 X Z4) K s, t j s2, t3, (st)2 > x Ka,b j a5 ,b4 ,ab-1a2b, a2b-1a-1b > 2 {sb2,stb2a,tb3,stsb} Z5 x S4 Ka j a5 > x K s,t j s2,t3, (st)4 > O {a2st, a3t2s, aststs, a4tst} M. Minchenko and I. M. Wanless: Quartic integral Cayley graphs 395 (Z5 x A4) x Z2 4 {tba2, bta, btbsb, tabs} < a, s,t,b | a5, s2, t3, b2, asa-1 s-1, ata-11-1, bsbt-1 st, (st)3, (tb)2, (ab)2 > Table 3: Bipartite Cayley QIGs Drawings for all but the three largest bipartite Cayley QIGs appear below. With over 70 vertices, it is difficult to present Gi5, Gi6, and G17 clearly. Gi G2 G3 396 Ars Math. Contemp. 8(2015)381-408 Gi Gii Gi2 Gi Gi Table 4: Drawings of quartic bipartite integral Cayley graphs G1 to G14 4.2 Bipartite arc-transitive integral graphs We considered all arc-transitive 4-regular graphs from the census of Potocnik et al. [17, 18] and tested them for integrality. The only arc-transitive bipartite QIGs that are not Cayley and thus not accounted for in Table 3 are the five that appear in Table 5. We let [r : H] = {Ha : a e r} denote the set of right cosets of H e r. A Schreier coset graph Sch(r, H, HSH) for a group r, subgroup H < r, and connection set S C r is the graph with vertex set [r : H] and with Ha connected to Hb if and only if ba-1 e HSH. We represent these 5 graphs as Schreier coset graphs. We give the order n and the spectrum [x, y, z, w] followed by the graph index from [17, 18]. Graphs appearing in the paper by Cvetkovic et al. are labelled with the notation of [7]: In,index. The first line consists of the group r, with a presentation of that group. The second line consists of the subgroup H and its generators in terms of the generators of r followed by the connection set S in terms of the generators of r. Group Subgroup, Subset Fi : n = 60 [4,16, 4, 5] I6o,i AT4Val[60][4] Z2 x Z2 x S5 : < a | a2 > x < b | b2 > x < s,t | s2,t5, (st)4, (st2st3)2 > D8 : < bstst2st-1,abstst >, {s,bt2, st ,bt-2} M. Minchenko and I. M. Wanless: Quartic integral Cayley graphs 397 F 2 : n = 70 [6,14,14, 0] Iro,i AT4Val[70][4] Z2 x S7 : x < s,t | s2 ,t7, (st)6, (st2st5)2, (stst-1)3 > S3 x S4 : < t2st-2,t-2st-1(st)2t,t2(st)2(ts)3t-1,t(st)2(ts)3,stst-1s >, {ast4, atstst-1, at, at-1} F3 : n = 90 [9,16,19, 0] Igo,i AT4Val[90][1] Z2 x PrL(2, 9): x (Z2 x D8) x Z2 : < yzxy-1x,x-1yxzx-1y,x2zy-1x-1y-1xy >, {ayx-1y-1x, az, ayxy-1x, axy-1x-1y} F4 : n = 180 [22, 28, 34, 5] AT4Val[180][12] Z2 xS3 xS6 : x < s,t | s2,t3, (st)2 > x < u,v | u2,v5, (uv)4, (uv2 uv3)2 > D8 : < v-2uv2 ,vuv2uv2 ,astuvuv2uv-1 >, {at-1v-2 ,atuv2 ,su,atv2} F5 : n = 210 [27, 28, 49, 0] AT4Val[210][10] S7 : S4 : , {t3s,st4, (st)3, (ts)3} Table 5: Bipartite arc-transitive non-Cayley QIGs The census [17, 18] of arc-transitive graphs contains all arc-transitive graphs with at most 640 vertices. Thus, the upper bound of 560 given in [25] for the order of a bipartite QIG, ensures that Table 3 and Table 5 contain all bipartite arc-transitive QIGs. The non-bipartite arc-transitive QIGs will be given in Sections 4.4 and 4.5. However, first we describe our method for finding all Cayley QIGs. 4.3 Integral graphs as quotients Let V(G) denote the vertices of a graph G, and E(G) the unordered pairs of vertices which are edges of G. A homomorphism from a graph G to a graph H is a map V(G) ^ V(H) which preserves adjacency. Each homomorphism induces an edge map E(G) ^ E(H). If the vertex and edge maps of the homomorphism are both surjective then we say that H is a quotient of G. In this section we find new integral graphs that are quotients of the integral graphs found in Table 3 and Table 5. To specify a quotient of a graph G it suffices to know G and the vertex map (the edges of the quotient are implied by the surjectivity of the edge map). We start by considering special classes of possible homomorphisms. A voltage assignment a for a graph G is a function from the arcs of G to a group r such that a((u, v)) = a((v, u))-1 for all {u, v} G E(G). The derived graph Vol(G, r, a) is the graph with vertex set the Cartesian product V(G) x r with (u, x) connected to (v, y) whenever {u, v} G E(G) and y = x * a((u, v)), where * is the group operation of r. Projection onto the first 378 Ars Math. Contemp. 8 (2015) 365-398 coordinate, by definition, maps the derived graph of Vol(G, r, a) onto G, and this map is a surjective homomorphism. Hence G is a quotient of the derived graph. As an interesting example for quartic integral graphs, we found a voltage assignment a for which the derived graph Vol(F1, Z3, a) is isomorphic to F4. Thus, F1 is a quotient of F4. Given two graphs G1, G2 with vertex sets V(G1), V(G2), let G1 x G2 be the graph with vertex set the Cartesian product V(G1) x V(G2) with (u1, W2) adjacent to (w1, W2) whenever both u1 is adjacent to w1 in G1 and u2 is adjacent to w2 in G2. The bipartite double cover of G is the bipartite graph G x K2 where K2 denotes the complete graph on two vertices. Equivalently, G x K2 is the derived graph Vol(G, Z2, a), where a is the constant function assigning 1 to every arc of G. We give an example for quartic integral graphs that was also noted in [7]. An odd graph Oi is the graph with one vertex for each of the (i - 1)-element subsets of a (2i - 1)-element set and with edges joining disjoint subsets. The graph F2 is the bipartite double cover of the integral graph O4. Similar to the result by Schwenk [20] used in [24] and [25], we have that if G is a QIG, then the bipartite double cover of G is a bipartite QIG. If G is a bipartite QIG then the bipartite double cover consists of two disjoint copies of G. For this reason, we have restricted our search to integral graphs that are bipartite up to this point. However, we now want to find all graphs which have their bipartite double cover among the bipartite graphs that we have discovered. This requires us to find quotients of our bipartite graphs. Since it is computationally easy to do, we will actually consider a more general class of homomorphisms than what is required for the task just described. This will increase the number of quartic integral graphs that we find. However, we make no effort to be exhaustive in finding all possible quotients. A graph automorphism is k-semiregular if all its orbits have the same size, k. Note that if G = H x K2 then the natural homomorphism from G onto H maps orbits of a 2-semiregular automorphism of G to single vertices of H. With this as motivation, the class of homomorphisms that we consider is the following. We identify any k-semiregular automorphism, $ of a target graph G. Our homomorphism is to collapse each orbit of $ to a single point. We wrote a routine in Magma [21] to find such quotients of a target graph G, as follows. For one representative, $, of each conjugacy class of (nontrivial) semiregular automorphisms of G, we collapsed the orbits of $ to single vertices to obtain a quotient H. If H was a 4-regular graph we checked to see if it was integral. If it was, then we printed it out and called the routine recursively on H. In some cases we were only interested in finding those H for which G is a bipartite double cover. In such instances, it suffices to only consider 2-semiregular automorphisms and we do not need to make recursive calls to the routine. We applied our Magma routine to all target graphs Gi for i e 1,..., 17 and to most of the arc-transitive graphs from the census of Potocnik et al. [17, 18]. There are graphs in the census with extremely large automorphism groups, and they were impractical for our simple routine. So we decided to only include target graphs from the census if their automorphism group had order no more than 220. The results of our Magma routine will be given in the following subsections. M. Minchenko and I. M. Wanless: Quartic integral Cayley graphs 399 4.4 Non-bipartite Cayley integral graphs In this section we report all quartic Cayley integral graphs that are not bipartite. We rely on this Lemma: Lemma 4.2. If G is a 4-regular Cayley graph then G x K2, the bipartite double cover of G, is isomorphic to a 4-regular Cayley graph. Proof. If G = Cay(r, S) then we define G' = Cay(T x Z2, {(s, 1) : s € S}). This graph G' is an undirected Cayley graph. It is not hard to verify that G' is isomorphic to G x K2 which gives the desired result. □ Hence we can find all the graphs we seek by applying the Magma routine of Section 4.3 to our graphs Gj where i = 1,..., 17. We use the following result by Sabidussi [19] to decide which of the graphs that we find are Cayley graphs: Lemma 4.3. A graph G is a Cayley graph if and only if Aut(G) contains a regular subgroup. Initial Graph #Non-bipartite #Cayley #Vertex-transitive #Arc-transitive Gi 0 0 0 0 G2 1 1 1 1 G3 1 1 1 1 G4 0 0 0 0 G5 1 1 1 0 G6 2 1 1 1 Gr 2 1 1 1 Gg 4 2 2 0 G9 0 0 0 0 G10 1 0 1 1 Gii 0 0 0 0 G12 2 1 1 0 G13 1 1 1 0 G14 2 2 2 0 G15 5 1 1 1 Gi6 13 2 2 0 G17 2 1 1 0 Table 6: Non-bipartite graphs found for Gj Table 6 summarizes our results using the Magma routine of Section 4.3 when restricted 378 Ars Math. Contemp. 8 (2015) 365-400 to the 2-semiregular automorphisms for each given Gi. We give the number of non-bipartite graphs found, followed by the numbers of those that are Cayley, vertex-transitive, and arc-transitive. The non-bipartite graphs counted in column 2 up to row 8 of Table 6 were previously found by Stevanovic et al. [25]. All graphs counted by column 2 from rows 9 to 17 were previously unknown with the exception of the graph with bipartite double cover Gio and one of the two graphs with bipartite double cover G14. In Table 7, we expand upon the counts of non-bipartite Cayley graphs in column three of Table 6 by producing a breakdown of the groups and the connection sets of the underlying graphs. We follow the same conventions as in Table 3 except that we use different notation for the spectrum, since there is no longer symmetry about the origin. Group Connection Sets (#involutions S) Hi : n = 5 - 14,41 Ia,i AT4Val[5][1] Z5 0 {a3,a2,a4,a} H2 : n = 6 - 22, 03, 41 Ia,i AT4Val[6][1] S3 2 {st,t,t2,s} Z6 0 {a5,a2,a,a4} H3 : n = 8 - 23, 03, 21, 41 Is,2 Z4 X Z2 < a 1 a4 > X < b 1 b2 > 2 {a,a2,a3,b} Ds 2 {r,r2,r3, fr2} 4 {f, r2 ,rf, fr} Z2 X Z2 X Z2 < a 1 a2 > X < b 1 b2 > X < c | c2 > 4 {b, a, abc, ac} H4 : n = 9 - 24,14, 41 19,2 AT4Val[9][1] Z3 X Z3 < a 1 a3 > X < b 1 b3 > 0 {a2b,ab2,a2,a} H5 : n = 12 - 25, 03, 23, 41 112,7 AT4Val[12][1] A4 < s,t 1 s2,t3, (st)3 > 0 {t2s,ts,st2,st} M. Minchenko and I. M. Wanless: Quartic integral Cayley graphs 4Û1 H« : n = 12 - 32,-14, O1,12, 22, 41 I 12,5 Z3 X Z4 O {a,ba2,b3a2,a2 } Z12 < a j a12 > O {a3,a4,a8,a9} D12 < r,f j r6,f2, (rf )2 > 2 {r4, fr4,r2, fr} 2 {r3, f,r4,r2} Z6 x Z2 < a j a6 > x < b j b2 > 2 {a2 ,b,a3, a4} Hr : n = 12 - 32, -22, O1,1«, 41 I12,1 Z3 x Z4 O {b3,b,b2a,b2a2} Z12 < a j a12 > O {a3,a10,a2,a9} D12 < r,f j r6,f2, (rf )2 > 2 {f, fr3,r, r5} 4 {r3, f, fr, fr5 } Z6 x Z2 < a j a6 > x < b j b2 > 2 {a3b, a3 ,a2b, a4b} H8 : n = 18 - 32, -24, O5,14, 32, 41 I18,4 Z3 x S3 < a j a3 > x < s, t j s2, t3, (st)2 > 2 {a,s,a2,st2} O {t,t2,sat2,sa2t2} (Z3 x Z3) X Z2 < a,b,c j a3 ,b3 ,c2 ,cac-1a-2 ,bc-1b-2c,aba-1b-1 > 2 {a,c,a2,cb2} Z6 x Z3 < a j a6 > x < b j b3 > O {a2 b, a5b2 ,ab, a4b2 } H9 : n = 2O - 2«, -14, O5, 34, 41 Z5 x Z4 2 {a2b2,ab2,a2b, a4b3} H10 : n = 24 - 33,-23,-15, O3,15, 21, 33, 41 I24,5 S4 2 {s,st2st, (tst)2,t(ts)2} Z2 x A4 2 {s,st2,a,ts} < a j a2 > x < s, t j s2, t3, (st)3 > 378 Ars Math. Contemp. 8 (2015) 365-402 H11 : n = 24 - 34, -23,-l2, O3, l8, 21, 32, 41 Z4 x S3 K a I a4 > x K s, t I s2 ,t3, (st)2 > 2 {a3t,at2,sa2,a2} (Za x Z2) x Z2 K a,b,c I a6,b2, c2,aba -1b-1, (a3c)2b, cbc-1b-1, a2 ca2 c > 4 {ca2,cb,b,a3} Z3 x Ds K a I a3 > x K r, f I r4,f2, (rf )2 > 2 {f, r2 , ar, a2 r-1 } Z2 x Z2 x S3 K a I a2 > x Kb I b2 > x K s,t I s2,t3,(st)2 > 4 {sabt, sbt2, ab, sa} H12 : n = 36 - 213 -l6, O3, l4, 23, 3®, 41 AT4Val[36][6] Z3 x A4 K a I a3 > x K s, t I s2 ,t3, (st)3 > 0 {ta, tst, t2a2, t2st2} H13 : n = 36 - 34, -210,O1,l16,34, 41 Z3 x (Z3 x Z4) K a,b,c I a3,b3,c4, aba -1b-1,aca-1c-1,bc-1b-2c> 0 {ac2b,cb2,a2c2b2 ,c3b2} (Z3 x Z3) x Z4 K a,b,c I a3,b3,c4, aba -1b-1 ,ac-1 a-1bc, ac2ac2 ,acbc-1b, 2 {a2bc3,a2c,ac2,ab2c2} c2bc2b > S3 x S3 K s, t I s2,t3, (st)2 > x K u,v I u2,v3, (uv)2 > 4 {suvt, s, sut2,uv2} Z6 x S3 K a I a6 > x K s, t I s2 ,t3, (st)2 > 2 {a5t2,at,sa3t,st} H14 : n = 36 - 34, -24,-l12, O1, l4, 2®, 34, 41 Z3 x (Z3 x Z4) K a,b,c I a3,b3,c4, aba -1b-1,aca-1c-1,bc-1b-2c> 0 {c3b,cb,a2b,ab2} (Z3 x Z3) x Z4 K a,b,c I a3,b3,c4, aba -1b-1 ,ac-1 a-1bc, ac2ac2 ,acbc-1b, 0 {a2bc3,a2c,b2,b} c2bc2b > S3 x S3 K s, t I s2,t3, (st)2 > x K u,v I u2,v3, (uv)2 > 2 {v2t,s,uv,vt2} Z6 x S3 K a I a6 > x K s, t I s2 ,t3, (st)2 > 2 {a2t,sa3t,a4t2,st} H15 : n = 6O - 34, -217,-l4, O15, 211, 38, 41 A5 K s, t I s2,t3, (st)5 > 2 {st2(st)2,tst2(st)2t, (st)3ts,((st)2t)2st} Table 7: Non-bipartite Cayley QIGs M. Minchenko and I. M. Wanless: Quartic integral Cayley graphs 403 Thus, by Theorem 4.1 and Lemma 4.2 we have that {G : 1 < i < 17} U {Hj : 1 < j < 15} is the complete set of Cayley QIGs. 4.5 Non-bipartite arc-transitive integral graphs In Section 4.2, we listed all bipartite arc-transitive QIGs from the census of Potocnik et al. [17, 18]. When searching this census for integral graphs, we also found arc-transitive QIGs that are not bipartite. There are 6 such graphs that are not Cayley and thus not already accounted for in Table 7. By [25], the bipartite double cover of any QIG has order at most 560, so we can be sure that the census contains all the arc-transitive QIGs. In fact, the following folklore result tells us more: Lemma 4.4. The bipartite double cover of an arc-transitive graph is arc-transitive. Proof. Let G be an arc-transitive graph. Then H = G x K2 has vertices (a, x) for all a G G and x G Z2 and arcs ((a, x), (b, x + 1)) and ((b, x), (a, x + 1)) whenever a is adjacent to b in G. It is not hard to show that the following maps are automorphisms of H : • (a, x) ^ (a(a), x + 1) for all a G G and x G Z2 where a G Aut(G). • (a, x) ^ (a, x + 1) for all a G G and x G Z2. Given these automorphisms, it is routine to check that H is arc-transitive. □ This last result provides a useful cross-check of our results and of the Magma routine from Section 4.3. It tells us that by applying the routine (restricted to 2-semiregular automorphisms) to the bipartite arc-transitive QIGs from Tables 3 and 5, we should find all the arc-transitive integral non-bipartite graphs. This list should tally with the list obtained by directly screening the census for integral graphs, which is what happened in practice. We now list the spectrum of the non-bipartite arc-transitive QIGs that are not Cayley and whose bipartite double cover is one of the Gj for i = 1,..., 17 or F for i = 1,..., 5. We denote these graphs by Jj for i = 1,..., 6. Graphs appearing in the paper by Cvetkovic et al. are included using the notation of [7]: /n,jndex. We give the graph index from the census ofPotocnik et al. [17, 18] in their notation: AT4Val[n][index]. • From G10, J1 = /15,2 = AT4Val[15][1] : [-25, -14, 25, 41], • From F1, J2 = AT4Val[30][2] : [-34, -25,-14,05, 211,41], J3 = I30,4 = AT4Val[30][3] : [-211,-14,05, 25, 34, 41], • From F2, J4 = I35,1 = AT4Val[35][2] = O4 : [-36, -114, 214, 41], • From F3, J5 = I45,1 = AT4Val[45][1] : [-216, -19,110, 39,41], • From F4, J6 = AT4Val[90][8] : [-314, -27, -124,05,110, 221, 38, 41]. Of the arc-transitive non-bipartite non-Cayley graphs, only J2 and J6 were not previously known to be integral. Thus, the arc-transitive QIGs from the census are as follows: G1, G2, G3, G5, G6, G7, G10, G11, G12, G15, G17, F1, F2, F3, F4, F5, H1, H2, H4, H5, H12, J1, J2, J3, J4, J5, and J6. We summarize these results by the following Lemma: Lemma 4.5. There are exactly 27 quartic integral graphs that are arc-transitive; 16 of which are bipartite. 378 Ars Math. Contemp. 8 (2015) 365-404 4.6 Other quartic integral graphs Finally, we list the spectra of the remaining QIGs which we found using the Magma routine of Section 4.3 in its full generality. These are graphs that are neither Cayley nor arc-transitive, but are quotients of the graphs Gj for i = 1,..., 17 and/or of the graphs AT4Val[n][index] for n < 640 with automorphism groups of order less than 220. We note that many of these graphs were obtained from multiple starting graphs, but we only list each graph once. We list the spectrum of the bipartite QIGs first. We denote these graphs by Mj for i = 1,..., 9 and follow the same conventions as in the list for Jj where i = 1,..., 6 except that we use the quadruple form for the spectrum of a bipartite graph. • From AT4Val[60][4] we have Mi ^ /30,3 : [1,8, 3, 2], • From G15 = AT4Val[72][12] we have M2 = /36,1 : [2,8,6,1], M3 = /36,2 : [3, 6, 5, 3], • From G17 = AT4Val[120][4] we have M4 : [3,4,1,6], M5 : [6,12, 2, 9], • From AT4Val[180][12] we have M6 : [9,16,19,0], M7 : [10,14,18, 2], • From AT4Val[216][12] we have M8 : [3, 5, 9,0], • From AT4Val[546][48] we have M9 : [5,4, 7,4]. We do not list graphs with at most 24 vertices since all bipartite QIGs on 24 or fewer vertices are known [25]. The 6 graphs M4,..., M9 were not previously known to be bipartite QIGs. We find that M6 is co-spectral to F3, but 5 of the above spectra were not previously known to be realized by any graph. Next, we list the spectrum of the non-bipartite QIGs. We denote these graphs by Lj where i G 1 , . . . , 44. • From AT4Val[30][3], L1 = /15,4 : [-25,-13,02,23,31,41]. • From G12 = AT4Val[36][3], L2 : [-33, -22, -11,05,13,22,31,41]. • From AT4Val[36][6], L3 ^ /18 5 : [-27, -12,01,14,21,32,41], L4 = /18,6 :[-26,-13,03, 12, 33, 41]. • From AT4Val[60][4], L5 : [-33, -27, -13,05,11,29,31,41], and L6 : [-32, -29,-12,05,12, 27, 32,41]. • From AT4Val[70][4], L7 : [-35, -24, -19,15,210, 31,41], and L8 : [-34, -26,-18,16, 28, 32, 41]. • From G15 = AT4Val[72][12], L9 : [-31, -25,-13,01,13, 23, 31, 41], L10 : [-32, -23, -14, 01,12, 25,41 ], Ln : [-32, -25, 01,16, 23,41], L12 : [-32, -24, -12, 01,14, 24,41 ], L13 : [-31, -25, -13, 01,13, 23, 31, 41], L14 : [-32, -24, -11, 03,14, 22, 31, 41], L15 : [-33, -29,-15,03,15, 27, 33, 41], L16 : [-34, 29,-12, 03,18, 27, 32, 41], L17 : [-32, -211,-14,03,16, 25, 34, 41], and L18 : [-33, -29, -15, 03,15, 27, 33, 41]. • From G16, L19 : [-34, -27,-16, 01,110, 23, 34,41], L20 : [-34, -29, -12, 01,114, 21, 34,41], L21 : [-34, -25, -110,01,16, 25, 34,41], L22 : [-34, -26, -18,01,18, 24, 34,41], M. Minchenko and I. M. Wanless: Quartic integral Cayley graphs 405 L23 : [—34, —28, — 14, 01,112, 22, 34,41], L24 : [—34, —26, — 18, 01,18, 24, 34,41], L25 : [—34, —28, — 14, 01,112, 22, 34,41], L26 : [—33, —27, — 19, 01,17, 23, 35,41], L27 : [—33, —28, —17, 01,19, 22, 35,41], L28 : [—34, —27, — 16, 01,110, 23, 34, 41], and L29 : [—34, —26, — 18, 01,18, 24, 34, 41]. • From AT4Val[90][1], L30 : [—34, —210, —19,110, 26, 35,41]. • From AT4Val[90][8], L31 : [—35, —26, —114,15,210, 34,41]. • From G17 = AT4Val[120][4], L32 : [—33, —27, —11,09,11,25,33,41], L33 : [—33, —27, —11, 09,11, 25, 33, 41], L34 : [—34, —25, —12,09, 27, 32, 41], L35 : [—37, —213, —13,015,11, 215, 35,41]. • From AT4Val[180][12], L36 : [—34, —28, —112,02,16, 26, 36,41], L37 : [—39, —217, —119, 05,115, 211, 313, 41], L38 : [—311, —213, — 121,05, 113,215, 311,41], and L39 : [—312, —215, —114,05, 120, 213, 310,41]. • From AT4Val[210][10], L40 : [—316, —29, —129,120, 219,311,41]. • From AT4Val[273][4], L41 : [—31, —24, —16,04,11,34,41]. • From AT4Val[546][48], L42 : [—32, —23, —15,04,12,21, 33,41], L43 : [—33, —22, —14, 04,13, 22, 32, 41], L44 : [—33, —22, —14,04,13, 22, 32, 41]. We do not list graphs with at most 12 vertices since all non-bipartite QIGs on 12 or fewer vertices are known [25]. Of the 44 graphs given above, only L1, L3 and L4 previously appear in the literature about integral graphs. The remaining 41 non-bipartite QIGs are new. 5 Concluding remarks There are precisely 32 connected 4-regular integral Cayley graphs up to isomorphism. Table 3 lists the 17 graphs of the 32 which are bipartite and Table 7 gives the details of the 15 non-bipartite graphs. There are exactly 27 quartic integral graphs that are arc-transitive. We found that 16 of the 27 graphs are bipartite; these appear in Table 3 and Table 5. We found that 16 of the 27 graphs are Cayley graphs; these appear in Table 3 and Table 7. There are integral Cayley bipartite graphs that can be decomposed into H x K2 where H is Cayley and arc-transitive, Cayley but not arc-transitive, or arc-transitive but not Cayley. The graph G10 is our only example of this last possibility; refer to Table 6. The new 4-regular integral graphs that we found that are co-spectral to other graphs are as follows: G13 co-spectral to 140,1 and 140,2, G15 to 172,1, H9 to 120,8, H12 to 136,4, and F3 to M6. We also mention the co-spectral graphs among the known integral graphs: G5 is co-spectral to 116,2 and another graph appearing in [25], G6 to 118,2 and 118,3, G7 to 124,1, F1 to /60,2, H5 to /12,6, and J3 to /30,5. We find that some integral Cayley graphs are co-spectral to integral non-Cayley graphs and that some integral arc-transitive graphs are co-spectral to integral graphs that are not arc-transitive. For example, the arc-transitive Cayley graph H5 has a co-spectral mate /12,6, that is neither arc-transitive nor Cayley. As can also be seen in Table 3, there are isomorphic integral graphs that are non-equivalent Cayley graphs Cay(T, S) and Cay(r*, £*) in the sense of Definition 1.1. This 406 Ars Math. Contemp. 8(2015)381-408 can occur for r = r* as well as r = r* with S = S*. Consider G12, which has 12 non-equivalent Cayley Graphs on 6 different groups. For r = S3 x S3, there are 4 non-equivalent Cayley graphs with connection sets occurring for each of the three possible numbers of involutions. There is only one Cayley graph up to equivalence for the graph of order 40. For all other orders the bipartite integral Cayley graphs are not unique up to equivalence. In the non-bipartite case; Hi, H4, H5, H9, Hi2, and H15 are all unique up to equivalence. There are non-isomorphic integral Cayley graphs with the same number of vertices. As can be seen in Table 3 for the bipartite case, there are two graphs on 12 vertices, three graphs on 24 vertices, and two graphs on 72 vertices up to isomorphism. For all other orders there is at most one graph up to isomorphism. There are many more examples in the non-bipartite case (refer to Table 7). There exist non-isomorphic integral Cayley graphs for the same group r. Consider Gj for i = 7,8,9 in Table 3. The following 6 groups are examples of this: Z2 x A4, Z3 x D8, Z2 x Z2 x S3, S4, (Z6 x Z2) x Z2, and Z4 x S3. We began with the 828 possible spectra from [25], and then narrowed our focus to a set S of 59 candidates for vertex transitive graphs; refer to Table 1 and Appendix A. Of these, we found 22 which are realised by Cayley graphs or arc-transitive graphs. In Section 4.6, by taking quotients, we found 6 new bipartite integral graphs that are neither arc-transitive nor Cayley, but realize a possible spectrum. Overall, we found 9 bipartite quartic integral graphs (namely, G16, G17, F4, F5, M4, M5, M7, M8, M9) that realise spectra not previously known to be achieved. It remains open whether the remaining possible spectra are realized by any 4-regular bipartite integral graphs. All integral graphs discovered in this paper are available in Magma format from: http://users.monash.edu.au/~iwanless/data/graphs/ IntegralGraphs.html. Acknowledgements A special thanks to Marston Condor, Heiko Dietrich, and Csaba Schneider for their helpful advice and for confirming some of our computational results. The authors used a mixture of the computer algebra packages Magma [21] and GAP [9] (including the GRAPE package [22] for GAP), as well as nauty [14]. This research formed part of the first author's PhD thesis [15]. A Feasible vertex-transitive spectra The following is the set S of possible spectra that might be realized by a connected 4-regular bipartite integral graph G that is vertex-transitive. This set was determined in Section 2. The entries are given as nxyzw [C4] [C&] where |V (G)| = n and Sp(G) = {4, 3x, 2y, 1z, 02w,-1z,-2y, -3x, -4}. M. Minchenko and I. M. Wanless: Quartic integral Cayley graphs 407 8 0 0 0 3 36 96 10 0 0 4 0 30 130 12 0 1 4 0 27 138 12 0 2 0 3 30 112 16 0 4 0 3 24 128 18 0 4 4 0 18 162 20 0 5 4 0 15 170 24 0 8 0 3 12 160 24 2 2 6 1 30 124 24 3 0 5 3 42 80 30 0 10 4 0 0 210 30 3 2 9 0 30 130 30 4 1 4 5 45 60 32 0 12 0 3 0 192 36 4 4 4 5 36 84 36 5 1 7 4 45 66 40 4 6 4 5 30 100 42 6 0 14 0 42 98 48 6 4 10 3 36 96 60 4 16 4 5 0 180 60 6 9 14 0 15 170 60 7 8 9 5 30 100 60 8 7 4 10 45 30 60 9 1 19 0 45 90 70 6 14 14 0 0 210 72 11 4 13 7 54 24 72 6 16 10 3 0 192 72 8 10 16 1 18 156 72 9 10 7 9 36 60 90 12 13 4 15 45 0 90 13 7 19 5 45 60 90 8 22 4 10 0 150 90 9 16 19 0 0 210 96 12 12 20 3 24 128 120 12 28 4 15 0 120 120 13 22 19 5 0 180 120 15 20 9 15 30 40 120 16 14 24 5 30 100 120 19 6 29 5 60 20 126 13 28 7 14 0 126 126 20 7 28 7 63 0 144 16 28 16 11 0 144 144 20 16 28 7 36 72 168 20 28 28 7 0 168 180 20 40 4 25 0 60 180 21 34 19 15 0 120 180 22 28 34 5 0 180 180 26 19 34 10 45 30 210 27 28 49 0 0 210 240 28 52 4 35 0 0 240 30 40 34 15 0 120 280 34 56 14 35 0 0 288 36 52 28 27 0 48 360 46 64 34 35 0 0 360 47 58 49 25 0 60 360 48 52 64 15 0 120 420 55 70 49 35 0 0 480 64 76 64 35 0 0 560 76 84 84 35 0 0 References [1] A. Abdollahi and M. Jazaeri, Groups all of whose undirected Cayley graphs are integral, European J. Combin. 38 (2014), 102-109. [2] A. Abdollahi and E. Vatandoost, Which Cayley graphs are integral?, Electron. J. Combin. 16 (2009), R122, 17pp. [3] A. Abdollahi and E. Vatandoost, Integral quartic Cayley graphs on abelian groups, Electron. J. Combin. 18 (2011), P89, 14pp. [4] A. Ahmady, J. P. Bell and B. Mohar, Integral Cayley graphs and groups, SIAMJ. Discrete Math. 28 (2014), 685-701. 378 Ars Math. Contemp. 8 (2015) 365-408 [5] N. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge, 1974. [6] D. M. Cvetkovic, Graphs and their spectra, Ph.D. thesis, University of Belgrade, 1971. [7] D. M. Cvetkovic, S. K. Simic and D. Stevanovic, 4-regular integral graphs, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 9 (1998), 89-102. [8] I. Estelyi and I. Kovacs, On groups all of whose undirected Cayley graphs of bounded valency are integral, Electron. J. Combin. 21 (2014), P4.45. [9] The GAP Group, GAP - Groups, Algorithms, and Programming, Version 4.5.7, 2012, http: //www.gap-system.org. [10] C. D. Godsil and G. Royle, Algebraic Graph Theory, Springer-Verlag, New York, 2001. [11] A. J. Hoffman, On the polynomial of a graph, Amer. Math. Monthly 70 (1963), 30-36. [12] W. Klotz and T. Sander, Integral Cayley graphs over abelian groups, Electron. J. Combin. 17 (2010), R81, 13pp. [13] C. H. Li, On isomorphisms of finite Cayley graphs: A survey, Discrete Math. 256 (2002), 301334. [14] B. D. McKay, nauty user's guide (version 2.4), 2009, http://cs.anu.edu.au/ ~bdm/ nauty. [15] M. Minchenko, Counting subgraphs of regular graphs using spectral moments, Ph.D. thesis, Monash University, 2014. [16] M. Minchenko and I. M. Wanless, Spectral moments of regular graphs in terms of subgraph counts, Linear Algebra Appl. 446 (2014), 166-176. [17] P. Potocnik, P. Spiga and G. Verret, Bounding the order of the vertex-stabiliser in 3-valent vertex-transitive and 4-valent arc-transitive graphs, arXiv:1010.2546v1 (2010). [18] P. Potocnik, P. Spiga and G. Verret, Cubic vertex-transitive graphs on up to 1280 vertices, J. Symbolic Comput. 50 (2013), 465-477. [19] G. Sabidussi, Vertex-transitive graphs, Monatsh. Math. 68 (1964), 426-438. [20] A. J. Schwenk, Computing the characteristic polynomial of a graph, in: R. Bari and F. Harary (eds.), Graphs and Combinatorics, Springer-Verlag, Berlin, volume 406 of Lecture Notes in Mathematics, pp. 153-172, 1974. [21] B. J. Smith, R package magma: Matrix algebra on GPU and multicore architectures, version 0.2.2, 2010, http://cran.r-project.org/package=magma. [22] L. H. Soicher, Grape-a gap package, version 4.6.1, http://www.maths.qmul.ac.uk/ -leonard/, May 17, 2012. [23] D. Stevanovic, Nonexistence of some 4-regular integral graphs, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 10 (1999). [24] D. Stevanovic, 4-regular integral graphs avoiding ±3 in the spectrum, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. (2003), 99-110. [25] D. Stevanovic, N. M. M. de Abreu, M. A. A. de Freitas and R. Del-Vecchio, Walks and regular integral graphs, Linear Algebra Appl. 423 (2007), 119-135.