/^creative ^commor ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 13 (2017) 275-291 Large circulant graphs of fixed diameter and arbitrary degree David Bevan University of Strathclyde, Glasgow, U.K. Grahame Erskine, Robert Lewis Open University, Milton Keynes, U.K. Received 9 November 2015, accepted 24 February 2017, published online 9 March 2017 Abstract We consider the degree-diameter problem for undirected and directed circulant graphs. To date, attempts to generate families of large circulant graphs of arbitrary degree for a given diameter have concentrated mainly on the diameter 2 case. We present a direct product construction yielding improved bounds for small diameters and introduce a new general technique for "stitching" together circulant graphs which enables us to improve the current best known asymptotic orders for every diameter. As an application, we use our constructions in the directed case to obtain upper bounds on the minimum size of a subset A of a cyclic group of order n such that the k-fold sumset kA is equal to the whole group. We also present a revised table of largest known circulant graphs of small degree and diameter. Keywords: Degree-diameter problem, Cayley graphs, circulant graphs, sumsets. Math. Subj. Class.: 05C25, 05C35 1 Introduction The goal of the degree-diameter problem is to identify the largest possible number n(d, k) of vertices in a graph having diameter k and maximum degree d. This paper considers the problem for the restricted category of circulant graphs, which we view as Cayley graphs of cyclic groups. We consider both undirected and directed versions of the problem in this paper. For a history and more complete summary of the degree-diameter problem, see the survey paper by Miller and Siran [5]. E-mail address: david.bevan@strath.ac.uk (David Bevan), grahame.erskine@open.ac.uk (Grahame Erskine), robert.lewis@open.ac.uk (Robert Lewis) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 276 Ars Math. Contemp. 13 (2017) 293-306 All groups considered in this paper are Abelian (indeed cyclic) and hence we use additive notation for the group operation. With this convention we define a Cayley graph as follows. Let G be an Abelian group and S C G a subset such that 0 G S. Then the Cayley graph Cay(G, S) has the elements of G as its vertex set and each vertex g has an edge to g + s for each s G S. The following properties of Cay(G, S) are immediate from the definition: • Cay(G, S) has order |G| and is aregular graph of degree |S|. • Cay(G, S) has diameter at most k if and only if every element of G can be expressed as a sum of no more than k elements of S. • Cay(G, S) is an undirected graph if S = -S; otherwise it is a directed graph. A circulant graph is a Cayley graph of a cyclic group, and we use these terms interchangeably. Throughout the paper we use the following notation: • CC(d, k) is the largest order of an undirected circulant graph with degree d and diameter k. • DCC(d, k) is the largest order of a directed circulant graph with degree d and diameter k. For a given diameter k, we are interested in determining the asymptotics of CC(d, k) and DCC(d, k) as the degree d tends to infinity. We make use of the following limits: • L-(k) = liminf CC(d,k)/df; L+(k) = limsup CC(d,k)/df. d^TO d^TO • LD(k) = liminf DCC(d,k)/df; L+ (k) = limsup DCC(d,k)/df. We begin with some trivial bounds on L- and L+. The following asymptotic upper bound is easily obtained; see for example the survey paper [5]: Observation 1.1 (Trivial upper bound). L+(k) < LD (k) < fj. For a lower bound, consider Zrk with generators {hr£ : |h| < [|J , 0 < I < k}: Observation 1.2 (Trivial lower bound). LD (k) > L-(k) > . In this paper, we present constructions which yield, for each k > 2, lower bounds on L- (k) and LD (k) that are greater than the trivial 1/kk bound. No such bounds were known previously. Our results include the following (see Corollary 4.6): • For any diameter k > 2 and any degree d large enough, CC(d, k) > (1.14775d)k. • For any diameter k that is a multiple of 5 or sufficiently large, and any degree d large enough, CC(d,k) > (1.20431 f)k. • For any diameter k > 2 andany degree d largeenough, DCC (d,k) > (1.22474 d )f. • For any diameter k that is a multiple of 6 or sufficiently large, and any degree d large enough, DCC(d, k) > (1.27378f)f. D. Bevan et al.: Large circulant graphs of fixed diameter and arbitrary degree 277 We also deduce a result concerning sumsets covering Zn, and use our techniques to construct a revised table of the largest known circulant graphs of small degree and diameter. For larger diameters, the trivial bounds become numerically small, and the ratio between the upper and lower bound becomes arbitrarily large. Therefore, in order more easily to assess the success of our constructions, we make use of the following measure which records improvement over the trivial lower bound. Let R-(k) = kL-(k)1/k, and define R+(k), RD(k) and RD(k) analogously. Thus, R- (k) > 1, with equality if the trivial lower bound is approached asymptotically for large degrees. For each k, these R values thus provide a useful indication of the success of our constructions in exceeding the trivial lower bound. In Section 4, we show how to construct a cyclic Cayley graph from two smaller ones in such a way that the R values are preserved. The R values are bounded above by Rmax(k) = k(k!)-1/k. Using the asymptotic version of Stirling's approximation, log k! ~ k log k - k, we see that as the diameter tends to infinity, 1 < liminf R-(k) < liminf R+(k) < e, k^w k^w and similarly for R- (k) and RD (k). In the next section, we extend a result of Vetrik [7] to deduce new lower bounds for L-(2) and R-(2). In Section 3, we describe a direct product construction and use it to build large cyclic Cayley graphs of small diameter and arbitrarily large degree. We also prove that this construction is unable to yield values that exceed the trivial lower bound for large diameter. However, in Section 4, we demonstrate a method of building a circulant graph by "stitching" together two smaller ones, and show how the application of this method to the constructions from Section 3 enables us to exceed the trivial lower bound for every diameter. Section 5 contains an application of our constructions to obtain upper bounds on the minimum size of a set A C Zn such that the k-fold sumset kA is equal to Zn. We conclude, in Section 6, by presenting a revised table of the largest known circulant graphs of small degree and diameter, including a number of new largest orders resulting from our constructions. 2 Diameter 2 bounds for all large degrees Much of the study of this problem to date has concentrated on the diameter 2 undirected case. In this instance, the trivial lower bound on L-(2) is 1/4 and the trivial upper bound on L+ (2) is 1/2. Vetrik [7] (building on Macbeth, Siagiova & Siran [4]) presents a construction that proves that L+ (2) > 3§ « 0.36111, and thus R+(2) > 1.20185. In this section, we begin by extending this result to yield bounds for L-(2) and R-(2). This argument can also be found in Lewis [3]. We reproduce it here for completeness, since we make use of the resulting bounds below. Vetrik's theorem applies only to values of the degree d of the form 6p - 2, where p is a prime such that p = 13,p ^ 1 (mod 13). We extend this result to give a slightly weaker bound valid for all sufficiently large values of d. The strategy is as follows: • Given a value of d, we select the largest prime p in the allowable congruence classes such that 6p - 2 < d. • We construct the graph of Vetrik [7] using this value of p. 278 Ars Math. Contemp. 13 (2017) 293-306 • We add generators to the Vetrik construction (and hence edges to the Cayley graph) to obtain a new graph of degree d which still has diameter 2. Note that the graphs in the Vetrik construction always have even order and hence we may obtain an odd degree d by adding the unique element of order 2 to the generator set. Success of this method relies on being able to find a prime p sufficiently close to the optimal value so that we need only add asymptotically few edges to our graph. We use recent results of Cullinan & Hajir [1] following Ramare & Rumely [6]. Lemma 2.1 (Cullinan & Hajir [1], Ramare & Rumely [6]). Let 5 = 0.004049. For any x0 > 10100 there exists a prime p = 2 (mod 13) in the interval [x0, x0 + 5xoj. Proof. We use the method of Cullinan and Hajir [1, Theorem 1]. This method begins by using the tables of Ramare and Rumely [6] to find a value e corresponding to k = 13, a = 2,x0 = 10100. Following the proof of Cullinan and Hajir [1, Theorem 1], if 5 > it follows that there must exist a prime p = 2 (mod 13) in the interval [x0, x0 + 5x0]. From Table 1, Ramare and Rumely [6] we find e = 0.002020 and hence 5 = 0.004049 will suffice. □ Our improved bound for circulant graphs of diameter 2 follows: Theorem 2.2 (see [3, Theorem 6]). L-(2) > 0.35820, and hence R-(2) > 1.19700. Proof. Let 5 = 0.004049 and let d > 10101. We seek the largest prime p = 2 (mod 13) such that 6p - 2 < d. By the result of Lemma 2.1, there exists such a p with p > (d + 2)/6(1 + 5). Let d' = 6p - 2. Then by the result of Vetrik [7] we can construct a circulant graph of degree d', diameter 2 and order n = H(d' + 2)(d' - 4). We can add d - d' generators to this construction to obtain a graph of degree d and diameter 2, with the same order n. Since n = 3§d2/(1 + 5)2 + O(d) « 0.358204d2 + O(d) the result follows. □ 3 Direct product constructions for small diameters In this section, we construct large undirected circulant graphs of diameters k = 3,4,5 and arbitrary large degree. We also construct large directed circulant graphs of diameters k = 2,..., 9 and arbitrary large degree. We then prove that the approach used is insufficient to yield values that exceed the trivial lower bound for large diameter. 3.1 Preliminaries The diameter 2 constructions of Macbeth, Siagiova & Siran and of Vetrik both have the form F+ x Fp x Zw for some fixed w and variable p, where F+ and Fp are the additive and multiplicative groups of the Galois field GF(p). Thus the first two components of their constructions are very tightly coupled, and this coupling is a key to their success. However, a significant limitation of this method is that it is only applicable in the diameter 2 case. In contrast, the constructions considered here have components that are as loosely coupled as possible. For diameter k, they have the form Zri x Zr2 x ... x Zrk x Zw for some fixed w and variable pairwise coprime r-j. This gives us greater flexibility, especially in terms of the diameters we can achieve. The price for this is that we lose the inherent structure of the finite field, which consequently places limits on the bounds we can achieve. D. Bevan et al.: Large circulant graphs of fixed diameter and arbitrary degree 279 The constructions in this section make use of the following result concerning the representation of each element of the cyclic group T = Zr x Zs (r and s coprime) as the sum of a small multiple of the element (1,1) and a small multiple of another element (u, v). It can be helpful to envisage T as a group of vectors on the r x s discrete torus. Lemma 3.1. Let u, d, s and m be positive integers with s > 1 and coprime to md. Let v = u + d. Suppose s > mv(u — 1). Then, for every element (x, y) of T = Zs+md x Zs, there exist nonnegative integers h < s + mv and £ < s — m(u — 1) such that (x,y) = h(1,1) + £(u,v). Observe that the construction ensures that (s + mv)(1,1) = m(u,v). Figure 1 illustrates the case with parameters u = 2, v = 5, s = 11, m = 2. Figure 1: Every element of Z17 x Zn is the sum of one of the 21 solid elements and one of the 9 circled elements. Proof. Let t = s — m(u — 1). Since s is coprime to md, (1,1) generates T. Hence, it suffices to show that, in the list (0,0), (1,1), (2,2), ..., the gaps between members of {£(u, v) : 0 < £ t — m, then we can take h' = muv and £' = £ + m — t = £ + mu — s: £(u,v) + muv(1, 1) = (£u + mu2 + mud, £v + muv) = (£u + mu2 + mud — u(s + 'md), £v + muv — vs) = (£ + mu — s)(u,v). The requirement that muv < s + mv is clearly equivalent to the condition on s in the statement of the lemma. □ 280 Ars Math. Contemp. 13 (2017) 293-306 In our direct product constructions, we make use of Lemma 3.1 via the following crucial lemma. Our strategy is to construct a cyclic group of the form T = Zri x Zr2 x ... x Zrk such that r1 > r2 > ... > rk > 1, and for each pair Zr. x Zrj for i < j we will bring Lemma 3.1 to bear. In the notation of that lemma we will set u = i, d = j — i, s = rj, s + md = ri. The conditions of Lemma 3.2 below are designed to ensure that for each pair i, j we can find m = mi,j to make this work. Lemma 3.2. Let k > 1 and let r1 > r2 > ... > rk be pairwise coprime integers greater than 1 such that ri is coprime to i for all 1 < i < k. Suppose that for each i,j with 1 < i < j < k there exists a positive integer mi,j such that: • ri — rj = mi,j (j — i) • rj > mi,j (i — 1) j. Let T = Zri x Zr2 x ... x Zrk. Let o = (1,1,..., 1), u = (1, 2,..., k) and, for each i, ei = (0,..., 1,..., 0) be elements of T, where only the ith coordinate of ei is 1, and let the set A consist of these k + 2 elements. Let co = maxi r2 + 2(r1 — r2) = r1 + (r1 — r2) > ri for all i. If S contains u but not o, omitting ei, then, since i and ri are coprime, we can choose hu such that i hu (mod ri) is the ith coordinate of x. Finally, if S contains both o and u, omitting ei and ej, then we can choose ho and hu by applying Lemma 3.1 to Zri x Zrj with (u, v) = (i, j). □ We note that the conditions of Lemma 3.2 imply that at most one of the ri can be even, and if k > 4 then all ri must be odd. 3.2 Undirected constructions We can use Lemma 3.2 to construct undirected circulant graphs of any diameter by means of the following theorem: Theorem 3.3. Let w and k be positive integers and suppose that there exist sets B and T ofpositive integers with the following properties: • B = {b1,..., bk+2} has cardinality k + 2 and the property that every element of Zw can be expressed as the sum of exactly k distinct elements of B U —B, no two of which are inverses. • T = {r1, r2,..., rk } has cardinality k and the properties that all its elements are coprime to w, and satisfies the requirements of Lemma 3.2, i.e. for each i < j: (a) ri > rj (b) gcd(ri,rj) = 1 (c) gcd(ri,i) = 1 D. Bevan et al.: Large circulant graphs of fixed diameter and arbitrary degree 281 (d) There is a positive integer mi,j such that equalities ri — rj = m^j (j — i) and rj > mj,j (i — 1)j hold. Let co = maxi ^ and L-(3) > ^, so R+(3) > 1.15455 and R-(3) > 1.14775. (b) L+(4) > L-(4) > gf6, so R+(4) > R-(4) > 1.16654. (c) L+(5) > L-(5) > , so R+(5) > R-(5) > 1.20431. Proof. Given a diameter k, the strategy is to find an optimal value of w which admits a set B satisfying the conditions of Theorem 3.3. We then seek an infinite family of positive integers q and a set A = {¿1, J2,..., such that for each of our values of q, the set T = {q, q — J1,..., q — ¿fc-1} satisfies the conditions of the theorem. We illustrate for k = 3. To prove (a) we take w = 57 and B = {1, 2, 7, 8,27}. It is easily checked that every element of Z57 is the sum of three distinct elements of B U — B, no two of which are inverses. Now we let A = {4,6}. For any q > 17, q = 5 (mod 6), q ^ 0,4,6 (mod 19) it is straightforward to verify that the set T = {q, q — 4, q — 6} satisfies the conditions of Theorem 3.3. In the notation of Lemma 3.2, we have co = q + 4. Taking a generating set X as defined in Theorem 3.3 we may construct a circulant graph of diameter 3, degree d = |X | = 10q — 12 and order 57q(q — 4)(q — 6) = ^ (d + 12) (d — 28)(d — 48). We can do this for an infinite number of values of q, and hence for an infinite number of values of d = 10q — 12 we have 57 CC(d, 3) > —(d +12)(d — 28)(d — 48). 282 Ars Math. Contemp. 13 (2017) 293-306 This yields L+(3) — T550O • Now we need to consider L-(3). The strategy will be to try to add "few" edges to our graphs to cover all possible degrees. Observe that we can use this construction for any q = 17 (mod 114) and hence for any d = 158 (mod 1140). Given any arbitrary even degree d, we can therefore find some d' no smaller than d — 1140 for which the construction works. We can then add d — d' generators to our graph to obtain a graph of the same order, degree d and diameter 3. However our graphs always have odd order, and so we are unable to obtain an odd degree graph by this method. To get round this problem we may use w = 56, B = {1, 2,7,14,15}, A = {2,4} and co = q + 2. Again it is easy to check that the relevant conditions are satisfied for any q — 15 such that q = 3,5 (mod 6) and q = 1, 3,5,6 (mod 7). Thenfor d = 10q—8 we can construct a graph of order 275 (d+8)(d—12)(d—32), degree d and diameter 3. We can do this for any q = 15 (mod 42) and hence for any d = 142 (mod 420). So given any arbitrary degree d, we can therefore find some d' no smaller than d — 420 for which the construction works, and then add d — d' generators to our graph to obtain a graph of the same order and diameter 3. (Since our graphs now have even order it is possible to add an odd number of generators.) Since the number of added generators is bounded above (by 419), the order of the graph is -25 d3 + O(d2). Result (a) for L-(3) follows. For (b) and (c) we adopt a similar method, except that in both cases the graphs used have even order and so our bounds on L+ and L- are equal. For brevity we show only the relevant sets in the construction, summarised as follows: (b) (k = 4) - Take w = 150, B = {1, 7,16, 26,41, 61} and A = {6, 8,12} so co = q + 6. Then for q — 49, q = 19 (mod 30) and d = 12q — 40, we have 25 CC(d, 4) — —— (d + 40)(d — 32)(d — 56)(d — 104). 3456 (c) (k = 5) - Take w = 436, B = {1,15,43,48,77,109,152} and A = {0,4,10,12, 16} so co = q + 8. Then for q — 77, q = 5 (mod 6), q = 0,1 (mod 5), q = 0,4,10,12,16 (mod 109) and d = 14q — 68, we have 109 CC(d, 5) — ——-(d +68)(d +12)(d — 72)(d — 100)(d — 156). 134456 □ 3.3 Directed constructions An analogous method yields directed circulant graphs via the following theorem: Theorem 3.5. Let w and k be positive integers and suppose that there exist sets B and T of non-negative integers with the following properties: • B = {0,62,..., bk+2} has cardinality k + 2 and the property that every element of Zw can be expressed as the sum of exactly k distinct elements of B. • T = {rT, r2,..., rk } has cardinality k and the properties that all its elements are coprime to w, and it satisfies the requirements of Lemma 3.2, i.e. for each i < j: (a) r > rj D. Bevan et al.: Large circulant graphs of fixed diameter and arbitrary degree 283 (b) gcd(rj, rj) = 1 (c) gcd(rj, i) = 1 (d) There is a positive integer mi,j such that equalities ri — rj = m^j (j — i) and rj > mi,j (i — 1)j hold. Let co = maxi §, so Rd(2) > 1.22474. (b) Ld(3) > ^fg, so Rd(3) > 1.24805. (c) Ld (4) > ^, so R-(4) > 1.26588. (d) Ld(5) > ^, so Rd(5) > 1.25881. (e) Ld(6) > ^, so Rd(6) > 1.27378. (f) Ld(7) > 159023, so Rd(7) > 1.26436. (g) Ld(8) > 25TO5000, so Rd(8) > 1.25206. (h) Ld(9) > 235r92r6Q1, so Rd(9) > 1.23939. Proof. The method is exactly the same as the proof of Theorem 3.4 and we summarise as follows: 284 Ars Math. Contemp. 1S (2G17) 275-291 (a) (k = 2) - Take w = 0, B = {0,1,2,4} and A = {2} so co = q + 2. Then for q > T, q = 1 (mod 0) and d = 4q — 1, we have - DCC(d, 2) > -(d + 1)(d — T). S (b) (k = -) - Take w = 9, B = {0,1, 2, -, 0} and A = {4, 0} so co = q + 4. Then for q > lT, q = B (mod 0) and d = Bq — T, we have DCC (d, -) > -^(d + T)(d — 1-)(d — 2-). l2B (c) (k = 4) - Take w =1-, B = {0,1, -, B, T, S} and A = {2,4, 0} so co = q + 2. Then for q > 2-, q = B (mod 0), q ^ 0, 2,4,0 (mod 1-) and d = 0q — 11, we have l- DCC (d, 4) > ——(d +11)(d — 1)(d — 1-)(d — 2B). 1290 (d) (k = B) - Take w = 1T, B = {0,1,2, -, 4, S, 1-} and A = {4,10,12,10} so co = q + S. Then for q > TT, q = B (mod 0), q ^ 0,1 (mod B), q ^ 0, 4, 10, 12,10 (mod 1T) and d = Tq — -B, we have IT DCC (d, B) > +-B)(d +T)(d — -B)(d — 49)(d — TT). (e) (k = 0) - Take w = 24, B = {0,1,2,4, S, 1-, 1S, 22} and A = {0,12,1S, 24, -0} so co = q + 0. Then for q > 1S1, q = 1, B (mod 0), q ^ 0,4 (mod B) and d = Sq — SB, we have - DCC (d, 0) > —— (d +SB)(d +-T)(d — 11)(d — B9)(d — 10T)(d — 1BB). -2T0S (f) (k = T) - Take w = -0, B = {0,1,2, 0, 9,12,10,1T, 1S} and A = {0, 2, 0,1S, 20, -0, 42} so co = q+42. Then for q > B29, q = 1 (mod 0), q = 4 (mod b), q ^ 0, 2, 0 (mod T), q ^ 9 (mod 11) and d = 9q — TT, we have DCC (d, T) > ———(d+TT)(d+B9)(d+2-)(d — SB)(d — 10-)(d — 19-)(d — -01). 1594-2- (g) (k = S) - Take w = -0, B = {0,1,2, -, 0,12,19, 20,2T, --} and A = {0, 0,12, 1S, 24, -0, -0,42} so co = q + 0. Then for q > -5-, q = 1,5 (mod 0), q = -(mod 5), q ^ 0,1 (mod T) and d = lOq — 10-, we have 9 DCC (d, S) > 2B000000 (d + 10-)(d + 10-)(d + 4-)(d — 1T) (d — TT)(d — 1-T)(d — 19T)(d — 2BT). (h) (k = 9) - Take w = 42, B = {0,1, 2, -, 4,9,10,20,20, -0, -T} and A = {0,2, 0, 12, 20, -0,42, 50, T2} so co = q + T2. Then for q > 109-, q = 1 (mod 0), q = -, 4 (mod 5), q = 1, -, 4 (mod T), q ^ 1, 0, 9 (mod 11), q ^ 4, T (mod 1-) and d = llq — 109, we have 42 DCC(d, 9) > 2-BT94T091 (d +109)(d + 14T)(d + 10-)(d +-T)(d — 51) (d — 101)(d — 29-)(d — 44T)(d — 02-). □ D. Bevan et al.: Large circulant graphs of fixed diameter and arbitrary degree 285 3.4 Limitations In [3], Lewis showed that an analogous class of constructions using finite fields to create graphs of diameter 2 is limited by the bound L-(2) < |. The constructions in this section have a similar limitation: Observation 3.7. Let k be a positive integer. The direct product constructions of Theorems 3.3 and 3.5 can never yield a lower bound on L-(k) or LD (k) that exceeds 2(++j^-i. Proof. First we consider the undirected case. Suppose the requirements of Theorem 3.3 hold and for each i = 1,..., k, we have ri = q — ai, where a1 < a2 < ... < a+. Let T = Zq_ai x ... x Zq_afc x Zw and X be its generating set as in the proof of Theorem 3.3. Since every element of Zw is a sum of k distinct elements of B, no pair of which are inverses, we must have w < (++2)2+ = (k + 1)(k + 2)2+~1. By the requirements of Lemma 3.2, for any i < j, we have mi j < ri - rj and co = maxi uvkikiW, i (b) R(ki + k2) > (R(ki)fclR(k2)fc^ fcl+fc2. Proof. (a) Let d > 1. For i = 1,2 we may construct graphs r of diameter kj, degree k d and order L(kj)(kjd)fci + o(dfci). Theorem 4.1 yields a product graph of diameter k i + k2, degree at most (k i + k2)d + 1 and order L(k i)L(k2)kkfcl kkk2dfcl+fc2 + o(dfcl+fc2). Part (b) follows by straightforward algebraic manipulation. □ In particular, we note that the stitching construction of Theorem 4.1 preserves lower bounds on the R values: R(mk) > R(k) for every positive integer m. We may use this idea to obtain better bounds for some particular diameters; for example we may improve on the undirected diameter 4 construction in Theorem 3.4: Corollary 4.3. (a) L+(4) > 2itg « 0.0081501, and hence R+(4) > 1.20185. (b) L-(4) > 0.0080194, and hence R-(4) > 1.19700. Proof. For statement (a) we note R+(2) > 3f from Vetrik [7] and apply Corollary 4.2 with k i = k2 = 2. For (b) we use the same method starting with Theorem 2.2. □ The stitching process of Theorem 4.1 can be iterated to produce a construction for any desired diameter, and Corollary 4.2 then gives us a lower bound for the R values for that diameter. We illustrate the results for small diameter k in Table 1. As an indicator of progress we show also the largest possible value of R for a particular k, given by Rmax(k) = k(k!)-i/k. It is worth noting that the method of Corollary 4.2 may be used to produce values of R which are larger than those achievable from the direct product constructions of Section 3. D. Bevan et al.: Large circulant graphs of fixed diameter and arbitrary degree 287 Table 1: The best R values for diameter k < 9. Diameter (k) 2 3 4 5 6 7 8 9 Rmax(k) ~ 1.41421 1.65096 1.80720 1.91926 2.00415 2.07100 2.12520 2.17016 R+(fc) > 1.20185° 1.15455d 1.20185c 1.20431d 1.20185f 1.20360f 1.20185f 1.20321f R-(fc) > 1.19700b 1.14775d 1.19700c 1.20431d 1.19700f 1.20222f 1.19700f 1.20105f Rd(k) > 1.22474e 1.24805e 1.26588e 1.25881e 1.27378e 1.26436e 1.26588f 1.26514f a. Vetrik [7]; b. Theorem 2.2; c. Corollary 4.3; d. Theorem 3.4; e. Theorem 3.6; f. Corollary 4.2 For example, the limitations noted in Observation 3.7 show that the maximum possible value of RD (10) we could achieve using Theorem 3.5 is approximately 1.26699. However, combining the results for diameters 4 and 6 in Table 1 yields R-(10) > 1.27061. Next we use our previous results to show that R is well-behaved in the limit. Theorem 4.4. Let L(k) be one of L-(k), L+(k), L^ (k) or Lj, (k), and let R(k) = kL(k)1/k. The limit R = lim R(k) exists and is equal to sup R(k). Proof. R(k) is bounded above (by e), so s = sup R(k) is finite. Hence, given e > 0, we can choose k so that s — R(k) < e/2. By Corollary 4.2 (b), R(mk) > R(k) for every positive integer m. Moreover, for any fixed j < k, since R(j) > 1, we have R(mk + j) > R(k)mk/(mk+j) > R(k)m/(m+1), which, by choosing m large enough, can be made to differ from R(k) by no more than e/2. □ Corollary 4.5. 5 x 1091/5 (a) lim R-(k) > 03/5 > 1.20431 k^TO 7 x 23/5 37/6 (b) lim RD (k) > ^^ > 1.27378 Proof. We choose the largest entry in the relevant row in Table 1. For (a) we know from Theorem 3.4 that L-(5) > y1^. For (b) we know from Theorem 3.6 that L^(6) > 215 . L-l We conclude this section by using the foregoing to derive new lower bounds for the maximum possible orders of circulant graphs of given diameter and sufficiently large degree. Corollary 4.6. (a) For any diameter k > 2 andany degree d large enough, CC (d, k) > (1.14775 k )k. (b) For any diameter k that is a multiple of 5 or sufficiently large, and any degree d large enough, CC(d,k) > (1.20431 f )k. (c) For any diameter k > 2 andany degree d large enough, DCC (d,k) > (1.224741 )k. (d) For any diameter k that is a multiple of 6 or sufficiently large, and any degree d large enough, DCC(d,k) > (1.27378f)k. 288 Ars Math. Contemp. 13 (2017) 275-291 Proof. (a) From Theorem 4.4 and Corollary 4.2, we know that R— (k) always exceeds the smallest value in the R— row of Table 1, which is 1.14775. (b) For k a multiple of 5, we know from Theorem 3.4 and Corollary 4.2 that R—(k) > 1.20431. The result for sufficiently large k follows from Corollary 4.5. (c) and (d) follow by using similar logic in the directed case. These represent significant improvements over the trivial bound of (f)k □ 5 Sumsets covering Zn Our constructions of directed circulant graphs can be used to obtain an upper bound on the minimum size, SS(n, k), of a set A c Zn for which the sumset kA = A + A + ... + A = Zn. The trivial bound is SS(n, k) < kn1/k which follows in the same way as the trivial lower bound for the directed circulant graph (see Observation 1.2). Improvements to this trivial bound do not appear to have been investigated in the literature. The idea is that, given S C Zn such that Cay(Zn, S) has diameter k, if we let A = 5 U {0} then kA = Zn. Our constructions thus enable us to bound SS(n, k) for fixed k and infinitely many values of n. For example, if we let L—(k) = liminf SS(n, k)/n1/k, then the following new result for k = 2 follows from Theorem 3.6 (a): Corollary 5.1. L— (2) < y^f - 1.63299. More generally, Corollary 4.5 shows that for large enough k and infinitely many values of n, SS(n, k) is at least 21 percent smaller than the trivial bound: Corollary 5.2. lim k-1 L—(k) < ^ - 0.78506. 6 Largest graphs of small degree and diameter We can use the construction of Theorem 4.1 to obtain large undirected circulant graphs for small degrees and diameters. Recently in [2], Feria-Puron, Perez-Roses and Ryan published a table of largest known circulant graphs with degree up to 16 and diameter up to 10. Their method uses a construction based on graph Cartesian products which is somewhat similar to ours. In contrast, however, Theorem 4.1 does not in general result in a graph iso-morphic to the Cartesian product of the constituents. Furthermore, our construction does not require the constituent graph orders to be coprime, which allows more graphs to be constructed. Using Theorem 4.1 allowed us to improve many of the entries in the published table. However, at the same time we developed a computer search which allows us to find circulant graphs of given degree, diameter and order. It turns out that this search is able to find D. Bevan et al.: Large circulant graphs of fixed diameter and arbitrary degree 289 larger graphs (at least in the range d < 16, k < 10) than the Theorem 4.1 method. We therefore present a much improved table of largest known circulant graphs based on the outputs of this search. In Table 2, we show the largest known circulant graphs of degree d < 16 and diameter k < 10. In Table 3 we give a reduced generating set for each new record largest graph found by the search. The computer search has been completed as an exhaustive search in the diameter 2 case up to degree 23, and these results are included in Table 3 for completeness. Table 2: Largest known circulant graphs of degree d < 16 and diameter k < 10. d \ k 1 2 3 4 5 6 7 8 9 10 2 3 5 7 9 11 13 15 17 19 21 3 4 8 12 16 20 24 28 32 36 40 4 5 13 25 41 61 85 113 145 181 221 5 6 16 36 64 100 144 196 256 324 400 6 7 21 55 117 203 333 515 737 1027 1393 7 8 26 76 160 308 536 828 1232 1764 2392 8 9 35 104 248 528 984 1712 2768 4280 6320 9 10 42 130 320 700 1416 2548 4304 6804 10320 10 11 51 177 457 1099 2380+ 4551+ 8288+ 14099+ 22805+ 11 12 56 210 576 1428+ 3200+ 6652+ 12416+ 21572+ 35880+ 12 13 67 275 819+ 2040+ 4283+ 8828+ 16439+ 29308+ 51154+ 13 14 80 312 970+ 2548+ 5598+ 12176+ 22198+ 40720+ 72608+ 14 15 90 381 1229+ 3244+ 7815+ 17389+ 35929+ 71748+ 126109+ 15 16 96 448 1420+ 3980+ 9860+ 22584+ 48408+ 93804+ 177302+ 16 17 112 518+ 1717+ 5024+ 13380+ 32731+ 71731+ 148385+ 298105+ f new record largest value Table 3: Largest circulant graphs of small degree d and diameter k found by computer search. d k Order Generators 6 2 21* 1, 2, 8 6 3 55* 1, 5, 21 6 4 117* 1,16, 22 6 5 203* 1, 7, 57 6 6 333* 1, 9, 73 6 7 515* 1,46, 56 6 8 737* 1,11,133 6 9 1027* 1,13,157 6 10 1393* 1, 92,106 7 2 26* 1, 2, 8 7 3 76* 1, 27, 31 7 4 160* 1, 5, 31 7 5 308* 1, 7, 43 7 6 536* 1, 231, 239 7 7 828* 1, 9, 91 7 8 1232* 1,11,111 7 9 1764* 1,803, 815 7 10 2392* 1,13,183 Continues on next page 290 Ars Math. Contemp. 13 (2017) 275-291 Table 3 - continued from previous page d k Order Generators 8 2 35* 1 6, 7,10 8 3 104* 1 16, 20,27 8 4 248* 1 61, 72, 76 8 5 528* 1 89, 156, 162 8 6 984* 1 163, 348, 354 8 7 1712* 1 215, 608, 616 8 8 2768 1 345,1072,1080 8 9 4280 1 429,1660,1670 8 10 6320 1 631, 2580, 2590 9 2 42* 1 5, 14, 17 9 3 130* 1 8, 14, 47 9 4 320* 1 15, 25,83 9 5 700* 1 5, 197, 223 9 6 1416 1 7, 575, 611 9 7 2548 1 7, 521, 571 9 8 4304 1 9, 1855, 1919 9 9 6804 1 9, 1849, 1931 9 10 10320 1 11, 4599, 4699 10 2 51* 1 2, 10, 16, 23 10 3 177* 1 12, 19, 27, 87 10 4 457* 1 20, 130, 147, 191 10 5 1099* 1 53, 207, 272, 536 10 6 2380 1 555,860, 951, 970 10 7 4551 1 739,1178,1295, 1301 10 8 8288 1 987, 2367, 2534, 3528 10 9 14099 1 1440, 3660, 3668, 6247 10 10 22805 1 218,1970, 6819, 6827 11 2 56* 1 2, 10, 15, 22 11 3 210* 1 49, 59, 84,89 11 4 576* 1 9, 75, 155, 179 11 5 1428 1 169, 285, 289, 387 11 6 3200 1 259, 325, 329,1229 11 7 6652 1 107, 647, 2235, 2769 11 8 12416 1 145,863, 4163, 5177 11 9 21572 1 663, 6257,10003,10011 11 10 35880 1 2209, 5127, 5135,12537 12 2 67* 1 2, 3,13, 21, 30 12 3 275* 1 16, 19, 29,86,110 12 4 819 7 26, 119, 143, 377, 385 12 5 2040 1 20, 24, 152, 511, 628 12 6 4283 1 19, 100, 431, 874,1028 12 7 8828 1 29, 420, 741, 2727, 3185 12 8 16439 1 151,840, 1278, 2182, 2913 12 9 29308 1 219,1011,1509, 6948, 8506 12 10 51154 1 39, 1378, 3775, 5447, 24629 13 2 80* 1 3, 9, 20, 25, 33 13 3 312* 1 14, 74, 77, 130, 138 13 4 970 1 23, 40, 76, 172, 395 13 5 2548 1 117,121, 391,481, 1101 13 6 5598 1 12, 216, 450, 1204, 2708 13 7 12176 1 45, 454, 1120,1632, 1899 13 8 22198 1 156,1166, 2362, 5999, 9756 13 9 40720 1 242, 3091,4615, 5162, 13571 13 10 72608 1 259,4815,8501, 8623, 23023 14 2 90* 1 4, 10, 17, 26, 29, 41 14 3 381* 1 11, 103, 120, 155,161, 187 14 4 1229 1 8, 105, 148, 160, 379, 502 Continues on next page D. Bevan et al.: Large circulant graphs of fixed diameter and arbitrary degree 291 Table 3 - continued from previous page d k Order Generators 14 5 3244 1 108, 244, 506, 709, 920, 1252 14 6 7815 1 197, 460, 696, 975, 2164, 3032 14 7 17389 1 123, 955, 1683, 1772, 2399,8362 14 8 35929 1 796, 1088, 3082, 3814, 13947, 14721 14 9 71748 1 1223, 3156, 4147, 5439,11841, 25120 14 10 126109 1 503, 4548, 7762, 9210, 9234, 49414 15 2 96* 1 2, 3, 14, 21, 31, 39 15 3 448* 1 10,127, 150, 176,189, 217 15 4 1420 1 20,111, 196, 264, 340, 343 15 5 3980 1 264, 300, 382, 668, 774, 1437 15 6 9860 1 438, 805, 1131, 1255, 3041, 3254 15 7 22584 1 1396, 2226, 2309, 2329,4582, 9436 15 8 48408 1 472, 2421, 3827, 4885, 5114, 12628 15 9 93804 1 3304, 4679, 9140,10144, 10160, 13845 15 10 177302 1 2193, 8578, 18202, 23704, 23716, 54925 16 2 112* 1 4, 10, 17, 29, 36, 45, 52 16 3 518 1 8, 36, 46, 75, 133,183, 247 16 4 1717 1 46,144, 272, 297,480, 582, 601 16 5 5024 1 380, 451, 811,1093, 1202, 1492, 1677 16 6 13380 1 395, 567, 1238, 1420,1544, 2526, 4580 16 7 32731 1 316, 1150,1797, 2909, 4460, 4836,16047 16 8 71731 1 749, 4314, 7798, 10918,11338,11471, 25094 16 9 148385 1 6094, 6964, 10683, 11704, 14274, 14332, 54076 16 10 298105 1 5860, 11313, 15833, 21207, 26491, 26722, 99924 17 2 130* 1 7, 26, 37, 47, 49, 52, 61 18 2 138* 1 9, 12, 15, 22, 42, 27, 51, 68 19 2 156* 1 15, 21, 23, 26, 33, 52, 61, 65 20 2 171* 1 11, 31, 36, 37, 50, 54,47, 65,81 21 2 192* 1 3, 15, 23, 32, 51, 57, 64, 85, 91 22 2 210* 2 7, 12, 18, 32, 35, 63, 70, 78, 91, 92 23 2 216* 1 3, 5, 17, 27, 36, 43, 57, 72, 83, 95 * proven extremal References [1] J. Cullinan and F. Hajir, Primes of prescribed congruence class in short intervals, Integers 12 (2012), #A56, http://www.integers-ejcnt.org/vol12.html. [2] R. Feria-Puron, H. Perez-Roses and J. Ryan, Searching for large circulant graphs, 2015, arXiv:1503.07357 [math.CO]. [3] R. R. Lewis, Improved upper bounds for the order of some classes of Abelian Cayley and circulant graphs of diameter two, 2015, arXiv:150 6.0284 4 [math.CO]. [4] H. Macbeth, J. Siagiova and J. Siran, Cayley graphs of given degree and diameter for cyclic, Abelian, and metacyclic groups, Discrete Math. 312 (2012), 94-99, doi:10.1016/j.disc.2011.03. 038. [5] M. Miller and J. Siran, Moore graphs and beyond: a survey of the degree/diameter problem, Electron. J. Comb. (2013), #DS14v2, http://www.combinatorics.org/ojs/index. php/eljc/article/view/DS14. [6] O. Ramare and R. Rumely, Primes in arithmetic progressions, Math. Comp. 65 (1996), 397-425, doi:10.1090/S0025-5718-96-00669-2. [7] T. Vetrik, Abelian Cayley graphs of given degree and diameter 2 and 3, Graphs Combin. 30 (2014), 1587-1591, doi:10.1007/s00373-013-1361-5.