A note on large graphs of diameter two and given maximum degree^{∗}

Brendan D. McKay

Department of Computer Science Australian National University Canberra, ACT 0200, Australia

e-mail: bdm@cs.anu.edu.au

Mirka Miller

Department of Computer Science and Software Engineering

The University of Newcastle, NSW 2308, Australia e-mail: mirka@cs.newcastle.edu.au

Jozef Širáň

Department of Mathematics SvF, Slovak Technical University

Radlinského 11, 813 68 Bratislava, Slovakia e-mail: siran@lux.svf.stuba.sk

∗This research was done while the third author was visiting the Department of Computer Science of the University of Newcastle NSW Australia in 1996, supported by small ARC grant of the second author.

Proposed running head:

Large graphs of diameter two and given degree

Corresponding author:

Jozef Širáň Department of Mathematics SvF, Slovak Technical University Radlinského 11 813 68 Bratislava Slovak Republic

Abstract

Let vt(d, 2) be the largest order of a vertex-transitive graph of degree d and diameter two. It is known that vt(d, 2) = d^{2} + 1 for d = 1, 2, 3, and 7; for the remaining values of d we have vt(d, 2) ≤ d^{2} − 1. The only known general lower bound on vt(d, 2), valid for all d, seems to be vt(d, 2) ≥ ⌊\frac{d+2}{2}⌋⌈\frac{d+2}{2}⌉.

Using voltage graphs, we construct a family of vertex-transitive non-Cayley graphs which shows that vt(d, 2) ≥ \frac{8}{9}(d + \frac{1}{2})^{2} for all d of the form d = (3q − 1)/2 where q is a prime power congruent with 1 (mod 4). The construction generalizes to all prime powers and yields large highly symmetric graphs for other degrees as well. In particular, for d = 7 we obtain as a special case the Hoffman-Singleton graph, and for d = 11 and d = 13 we have new largest graphs of diameter two and degree d on 98 and 162 vertices, respectively.

1 Introduction

The well-known degree/diameter problem asks for determining the largest possible number n(d, k) of vertices in a graph of maximum degree d and diameter k. For information about the current state of the general problem we refer to [1, 5, 6, 7, 8, 14]; in this note we focus only on the special case of graphs of diameter two. The equality in n(d, 2) ≤ d^{2} + 1 (where the right hand side is known as the Moore bound) is attainable only if d = 1, 2, 3, 7 and, possibly, 57; except possibly for the last value, the corresponding extremal graphs K_{2}, C_{5}, the Petersen graph and the Hoffman-Singleton graph are unique [15]. For the remaining d it was shown [10] that n(d, 2) ≤ d^{2} − 1; so far the only values of d for which this bound is known to be attained are d = 4 and 5 (see [9] for the extremal graphs).

The asymptotically best lower bound on n(d, 2) can be obtained as follows. Incidence graphs associated with finite projective planes [3] give the inequality n(d, 2) ≥ d^{2} − d + 1 for each d such that d − 1 is a prime power. (The paper [3] appeared a long time ago but somehow did not receive appropriate attention. As observed in [10] and rediscovered in [7], the bound can further be improved to n(d, 2) ≥ d^{2} − d + 2 if d − 1 is a power of 2.) For the remaining values of d, one can use the fact that for each d there is a prime between d and d + c_{ε}d^{7/12+ε} where ε > 0 is arbitrary and c_{ε} is a constant, see [16]. Combining this with vertex duplication in the graphs of [3] yields n(d, 2) ≥ d^{2} − c′_{ε}d^{7/6+ε} for some constant c′_{ε} and all d.

Nevertheless, not much is known about the vertex-transitive version of the problem. Let vt(d, 2) be the largest order of a vertex-transitive graph of degree d and diameter two. Obviously, we have the same upper bounds on vt(d, 2) as on n(d, 2), and the above comments are valid with two exceptions. First, there is no vertex-transitive graph of diameter two and degree 57, see [4]. Second, we do not know if the bound vt(d, 2) ≤ d^{2}−1 for d ≠ 1, 2, 3, 7 can be attained. As regards lower bounds, unfortunately, the graphs of [3] are not vertex-transitive. Presently, the best general result (that is, valid for all d) seems to be [12]

vt(d, 2) ≥ ⌊\frac{d + 2}{2}⌋ ⌈\frac{d + 2}{2}⌉ .  (1)

The inequality (1) comes from the Cayley graph C(Z_{⌊ \frac{d+2}{2} ⌋} ×Z_{⌈ \frac{d+2}{2} ⌉}, X) where the generating set X of the group consists of all elements (x_{1}, x_{2}) such that exactly one of x_{1}, x_{2} is equal to 0.

In view of the huge gap between the general lower bound (1) for vertextransitive graphs and the asymptotically best lower bound on n(d, 2), it would be highly desirable to have improvements over (1) for all d, or at least for infinitely many new values of d. In order to do so one has to extend the existing family of construction methods (cf. [1, 5, 6, 7]). The purpose of this note is to promote the covering graph technique, well known in topological graph theory, as a further suitable candidate for constructing large graphs with given degree and diameter. We justify this choice by showing how covering graphs can be used to construct highly symmetric graphs of diameter two, degree d, and order \frac{8}{9}(d + \frac{δ}{2})^{2} for d = (3q − δ)/2 where q = 4ℓ + δ is a prime power and δ ∈ {−1, 0, 1}. Moreover, if δ = 1 we show that the corresponding graphs are vertex-transitive and, interestingly enough, non-Cayley. Therefore vt(d, 2) ≥ \frac{8}{9}(d + \frac{1}{2})^{2} for d = (3q − 1)/2 where q is a prime power ≡ 1 (mod 4). Apart from a great improvement over (1) for such d, we note that if d = 7 we obtain the Hoffman-Singleton graph as a special case of our construction. Even more importantly, for d = 11 and d = 13 we obtain new largest graphs of diameter two and degree d on 98 and 162 vertices, respectively (the largest previously known orders were 94 and 136, cf. [8, 14]).

We prove our main result in Section 3. In order to make this note reasonably self-contained, in Section 2 we present a very brief introduction to (regular) covering graphs in terms of voltage assignments in finite groups. A good general reference on the topic is the book [13]; a more detailed account with emphasis on the degree/diameter problem is given in [2].

2 Voltage assignments and lifts

Let G be an undirected graph, possibly with loops and/or parallel edges and semiedges, that is, dangling edges with just one end incident to a vertex. Each edge (inclusive loops) which is not a semiedge can be assigned one of the two possible directions; an edge with a direction is called an arc. A semiedge has, by definition, only one possible direction (outward of the incident vertex).

In this way, every edge which is not a semiedge underlies a pair of mutually reverse arcs; the reverse of an arc e is denoted by e^{−1}. For convenience, if e is a semiedge we may still use the symbol e^{−1} but we understand that e = e^{−1} in such case. Let D(G) be the set of all arcs of G and let Γ be an arbitrary finite group. A mapping α : D(G) → Γ is a voltage assignment if, for each arc e ∈ D(G),

α(e^{−1}) = (α(e))^{−1} .  (2)

Observe that, by (2), for each semiedge e we have (α(e))^{2} = 1_{Γ}.

A graph G endowed with a voltage assignment α : D(G) → Γ gives rise to a new (larger) graph G^{α}, called a lift of G. The vertex set of the lift is V (G^{α}) = V (G) × Γ and the arc set of the lift is D(G) × Γ; in both cases we will denote the group coordinate by means of a subscript. The incidence in the lift is defined as follows. If e is an arc in the base graph G from a vertex u to a vertex v, then for each g ∈ Γ there is an arc e_{g} in G^{α} from the vertex u_{g} to the vertex v_{gα(e)}. Note that, by the same token, there also is an arc (e^{−1})_{gα(e)} in the lift from v_{gα(e)} to u_{g}. The arcs e_{g} and (e^{−1})_{gα(e)} are mutually reverse in the lift and, by definition, they form an undirected edge of G^{α}; hence the lift is an undirected graph.

The natural projection π : G^{α} → G which erases the subscripts is a graph homomorphism called a (regular) covering projection; the lift itself is a covering graph. The sets π^{−1}(u) and π^{−1}(e) are called fibres above a vertex u and an arc e. (The above “regularity” refers to the action of Γ on fibres.)

By a u→v walk of length m in the base graph G we understand a sequence W = e_{1}e_{2} … e_{m} where e_{i} are arcs of G, such that e_{1} emanates from u, e_{m} terminates at v, and the terminal vertex of e_{i−1} coincides with the initial vertex of e_{i}, 2 ≤ i ≤ m. (If, say, e_{i} is an arc arising from a semiedge, then its initial and terminal vertices are identical.) Now, if α is a voltage assignment on G in a group Γ, then the net voltage of W is simply the group product α(W) = α(e_{1})α(e_{2}) … α(e_{m}). For convenience, at each vertex we also admit a trivial walk of length 0 and of unit net voltage. An important fact is that for each u→v walk W in G and each g ∈ Γ there exists a unique walk W_{g}^{α} in the lift G^{α} emanating from u_{g} and such that π(W_{g}^{α}) = W; it has the same length as W and terminates at the vertex v_{gα(W)}. Conversely, if W̃ = ãb̃ … c̃ is a walk in the lift G^{α}, then π(W) = π(a)π(b) … π(c) is a walk in G (of the same length as W̃).

Finally, we note that the diameter of the lift can be determined using the following easy observation.

Lemma 1 Let α be a voltage assignment on a graph G in a group Γ. Then, diam(G^{α}) ≤ k if and only if for each ordered pair of vertices u, v (possibly, u = v) of G and for each g ∈ Γ there exists a u→v walk of length ≤ k of net voltage g.

Proof. Observe that for any two distinct vertices u_{g} and v_{h} in G^{α} there exists a u_{g}→v_{h} walk W̃ of length ≤ k if and only if the projection W = π(W̃) is a u→v walk in G of length ≤ k with net voltage α(W) = g^{−1}h. □

3 Results

We are now in position to state and prove the main results of this note.

Theorem 1 Let d be any number of the form d = (3q − δ)/2 where q is a prime power congruent with δ (mod 4), δ ∈ {−1, 0, 1}. Then there exists a graph H_{q} of degree d and diameter 2 whose order is \frac{8}{9}(d + \frac{δ}{2})^{2}.

Proof. Let q be a prime power of the form q = 4ℓ+δ where δ ∈ {−1, 0, 1}. As usual, by GF (q) we denote the Galois field of order q. We start with identifying a few auxiliary subsets of GF (q). Let ξ be a primitive element of GF (q). Let Y = {1, ξ^{2}, ξ^{4}, …, ξ^{2ℓ−2}} and let X = Y ∪ ξ^{2ℓ}Y if δ ∈ {0, 1} and X = Y ∪ ξ^{2ℓ−1}Y if δ = −1. Further, if δ ∈ {0, 1} we define Y′ = {ξ, ξ^{3}, …, ξ^{2ℓ−1}} and X′ = Y′ ∪ ξ^{2ℓ}Y′. For δ = −1 let Y′ = {1, ξ, ξ^{3}, …, ξ^{2ℓ−3}} and X′ = Y′ ∪ ξ^{2ℓ−1}Y′. It is easy to check that |X| = |X′| = 2ℓ, X ∪ X′ = GF (q) − {0}, and X ∩ X′ = ∅, {1}, or {−1, 1} according as δ = 1, 0, or −1. Note that both X and X′ are closed under taking additive inverses; this is clear if δ = 0, and for δ ≠ 0 one can easily verify that, in fact, X = Y ∪ −Y and X′ = Y′ ∪ −Y′. In addition, observe that X′ = ξX; for δ = 1 we also have X = ξX′.

Next, we introduce our base graph G. For δ ≠ 0 let G be the graph obtained from a complete bipartite graph K_{q,q} by attaching ℓ loops at each of the 2q vertices; if δ = 0 then we form G by attaching 2ℓ = q/2 semiedges at each vertex of K_{q,q}. For convenience we identify the vertex set of G with the product GF (q) × Z_{2} in the natural way, that is, no two distinct vertices with the same Z_{2}-coordinate are adjacent in G.

Let GF^{+}(q) denote the additive group of the Galois field. We now describe a voltage assignment α on D(G) in the group GF^{+}(q). We start with picking reference directions on edges of G as follows: Each loop is directed arbitrarily, and each edge joining a vertex (j, 0) with a vertex (k, 1) will be directed from (j, 0) to (k, 1). (As we know, semiedges have a unique direction.) The voltage assignment itself will be given by the following simple rules. Consider the case δ = 0 first. Then, for each vertex u = (j, 0) of G, α assigns to the 2ℓ semiedges u the voltages in X in any 1–1 way. Similarly, for each vertex v = (k, 1), we assign to the 2ℓ semiedges at v the voltages in X′ in an arbitrary 1–1 way. (This agrees with (2) because, for δ = 0, all elements in X ∪ X′ have additive order two.) If δ ≠ 0, then α assigns to the ℓ directed loops at each vertex u = (j, 0) the voltages in Y in any 1–1 fashion. By analogy, for each vertex v = (k, 1), we assign to the ℓ directed loops at v the voltages in Y′ in an arbitrary bijective way. Finally, for all δ, each arc e_{jk} from a vertex (j, 0) to a vertex (k, 1) will receive as its voltage the product α(e_{jk}) = jk. Voltages on arcs which are reverse to the above are given by (2).

Now we show that for any ordered pair of (not necessarily distinct) vertices (j, r) and (k, s) of the base graph G and for any element m of the voltage group GF^{+}(q) there exists a (j, r)→(k, s) walk in G of length at most two and of net voltage m. We distinguish several cases.

(a): j = k and r = s. We assume that r = 0; the argument for r = 1 is similar. Also, we may assume that m ≠ 0 now. If m ∈ X, then we have a (j, r)→(k, s) walk in G of length one (consisting of either a single loop or a single semiedge) of net voltage m. If m ∉ X, then (by a simple counting) the sets X and m + X have a nonempty intersection, and so there exist x, y ∈ X such that x = m + y. It follows that there is a (j, r)→(k, s) walk of length two and net voltage m in G, namely, the one consisting of the two loops (or two semiedges if δ = 0) with voltages x and −y.

As an interesting aside, we note that the above is equivalent to the fact that the subgraph of the lift G^{α} induced by the fibre above the vertex (j, r), i.e., the lift of the bouquet of the ℓ loops or 2ℓ semiedges at (j, r), is isomorphic to the Cayley graph C(GF^{+}(q), X) or C(GF^{+}(q), X′), both of diameter two. In addition, observe that the union of the two Cayley graphs is the complete graph of order q, and their intersection is edgeless, or a perfect matching, or a Hamilton cycle, depending on whether δ = 1, 0, or −1. In fact, for δ = 1 the first Cayley graph is known as the Paley graph P (GF (q), X), which is selfcomplementary and strongly regular.

(b): j ≠ k and r = s. We shall assume that r = 0; the proof is almost identical for r = 1. Let i = (j − k)^{−1}m; the multiplicative inverse exists in GF (q) because j ≠ k. Then, the walk (j, 0)→(i, 1)→(k, 0) has length two and net voltage ji − ik = (j − k)i = m.

(c): j ≠ k and r ≠ s. Again, assume that r = 0 and s = 1; the other case is similar. If m = jk, we take the length one walk (j, 0)→(k, 1) whose net voltage is m. If m ≠ jk and m − jk ∈ X, we take the length two walk in G of the form (j, 0)→(j, 0)→(k, 1) where the loop (or the semiedge) at the vertex (j, 0) has voltage m − jk ∈ X; clearly, the net voltage of the walk is m. Finally, if m − jk ∉ X then m − jk must belong to X′. In such case consider the walk (j, 0)→(k, 1)→(k, 1) in G where the loop (or the semiedge) at the vertex (k, 1) has voltage m − jk ∈ X′; again the net voltage of the walk is m.

Let H_{q} = G^{α} be the lift of G with respect to the voltage assignment α. Invoking Lemma 1, it follows that the diameter of H_{q} is at most two; in fact, it is equal to two. It is clear that the lift is a regular graph of degree d = q + (q − δ)/2 = (3q − δ)/2 = 6ℓ + δ, and its number of vertices is equal to |V (G)||GF^{+}(q)| = 2q^{2} = \frac{8}{9}(d + \frac{δ}{2})^{2}. The proof is complete. □

As regards symmetries of the lift G^{α} = H_{q}, computational evidence using the nauty package [17] shows that the graphs H_{q} are not vertex-transitive for q = 7, 8, 11, 16, 27 and 32. We suspect that the latter is true in general for prime powers q ≡ 0 or −1 (mod 4), q ≥ 7, and we do not see any easy modification of our construction which would make the graphs vertextransitive for these q. However, for the remaining prime powers we have the following result.

Theorem 2 If q is a prime power congruent to 1 (mod 4), then the graph H_{q} is vertex-transitive and non-Cayley. Consequently, vt(d, 2) ≥ \frac{8}{9}(d + \frac{1}{2})^{2} where d = (3q − 1)/2.

Proof. We recall that vertices of the lift H_{q} = G^{α} have the form (i, r)_{m} = (i, r, m), where (i, r) ∈ GF (q) × {0, 1} represent vertices of the base graph and m ∈ GF (q) are voltages. According to the definition of the lift, each vertex (i, r, m) is adjacent in G^{α} to the |X| vertices (i, r, m + ξ^{r}x), x ∈ X, as well as to the q vertices (j, 1 − r, m + (−1)^{r}ij), j ∈ GF (q). A simple verification shows that, for s, t ∈ GF (q), the functions f_{s}, g_{t} : V (G^{α}) → V (G^{α}) given by f_{s}(i, r, m) = (i, r, m + s) and g_{t}(i, r, m) = (i + t, r, m − (−1)^{r}it + rt^{2}) are automorphisms of the lift for any δ. It follows that the group ⟨f_{s}, g_{t}⟩ ≃ GF^{+}(q) × GF^{+}(q) acts on V (G^{α}) freely with exactly two orbits; this is valid for all prime powers q. For q ≡ 1 (mod 4) we have an additional automorphism h of G^{α} given by h(i, r, m) = ((−ξ)^{r}i, 1 − r, ξm). Clearly, in this case the group ⟨f_{s}, g_{t}, h⟩ acts transitively on the vertex set of H_{q}.

It remains to show that the graphs H_{q} are non-Cayley. This is known to be true for H_{5}, the Hoffman-Singleton graph, and therefore we assume that q = 4ℓ + 1 is a prime power grater than 5. For r = 0, 1, let V_{r} = {(i, r, m); i, m ∈ GF (q)}; clearly (V_{0}, V_{1}) is a partition of V (H_{q}). It is known [11] that each edge of the Paley graph P (GF (q), X), q > 5, lies in a triangle. Hence (see the remark in the part (a) of the preceding proof) the only edges of H_{q} which are not contained in a triangle are those from V_{0} to V_{1}. Consequently, (V_{0}, V_{1}) is a block system of the group Aut(H_{q}).

Next, we show that the group Aut(H_{q}) contains no involution τ such that τ(V_{0}) = V_{1}. Indeed, suppose the contrary and let τ(u_{0}) = u_{1} where u_{0} = (0, 0, m) and u_{1} = (j, 1, m′). Let m ≠ m′. Consider the case when m′−m ∈ X (the case m′−m ∈ X′ is analogous). Then there is exactly one path of length at most two in H_{q} between u_{0} and u_{1}, namely the path Q = u_{0}→w→u_{1} where w = (0, 0, m′). Since τ is an edge-preserving involution, we also have the length two path τ(Q) = u_{1}→τ(w)→u_{0}. By the uniqueness of w we have τ(w) = w, contrary to the assumption τ(V_{0}) = V_{1}. Finally, if m = m′, just take an arbitrary x ∈ X and consider the vertex v_{0} = (0, 0, m + x). Since u_{0}v_{0} is an edge of H_{q}, we have τ(v_{0}) = (j, 1, m′ + x′) = v_{1} for some x′ ∈ X′. But now m + x ≠ m′ + x′, and we can repeat the preceding argument with v_{0}, v_{1} in place of u_{0}, u_{1}.

The rest is easy. Suppose that the group Aut(H_{q}) contains a regular subgroup Λ. Since (V_{0}, V_{1}) is a block system for Λ, there is a θ ∈ Λ such that θ(V_{0}) = V_{1}. Because of regularity, all orbits of θ must have the same (even) length, say, 2t; as |V (H_{q})| = 2q^{2}, we see that t must be odd. But then τ = θ^{t} is an involution such that τ(V_{0}) = V_{1}, a contradiction. □

As remarked in the Introduction, the above construction gives, for d = 7, the Hoffman-Singleton graph [15]. For d = 11 and 13 we obtain graphs of diameter two on 98 and 162 vertices, which are larger than any of the previously known graphs of diameter two and degree 11 and 13 (compared with the values 94 and 136 contained in the tables of currently largest graphs of given degree and diameter in [8] or [14]). Especially, the new vertextransitive graph of order 162 is of great interest as it misses the Moore bound only by 8. For the next two degrees, d = 19 and 25, Theorem 1 yields vertex-transitive graphs of diameter two and degree d of order 338 and 578, respectively (the corresponding Moore bounds are 362 and 626).

References

[1] J. C. Bermond, C. Delorme, G. Farhi, Large graphs with given degree and diameter II, J. Combin. Theory (B) 36 (1984) 32-48.

[2] L. Branković, M. Miller, J. Plesník, J. Ryan, J. Širáň, Large graphs with small diameter and degree: A voltage assignment approach, submitted.

[3] W. G. Brown, On graphs that do not contain a Thompsen graph, Canad. Math. Bull. 9 (1966) 281-285.

[4] P. J. Cameron, Automorphism groups of graphs, in: Selected Topics in Graph Theory 2 (L. W. Beineke and R. J. Wilson, Eds.), Academic Press, 1983, 89-127.

[5] C. Delorme, Large bipartite graphs with given degree and diameter, J. Graph Theory 8 (1985) 325-334.

[6] C. Delorme, Examples of products giving large graphs with given degree and diameter, Discrete Applied Math. 37/38 (1992) 157-167.

[7] C. Delorme, Grands graphes de degré et diamètre donnés, European J. Combin. 6 (1985) 291-302.

[8] M. J. Dineen, P. R. Hafner, New results for the degree/diameter problem, Networks 24 (1994) 359-367.

[9] B. Elspas, Topological constraints on interconnection-limited logic, Proc. 5th Ann. Symp. Switching Circuit Theory and Logic Design (1964) 133-147.

[10] P. Erdős, S. Fajtlowicz, A. J. Hoffman, Maximum degree in graphs of diameter 2, Networks 10 (1980) 87-90.

[11] C. D. Godsil, “Algebraic Combinatorics”, Chapman and Hall, 1993, Sect. 10.2.

[12] T. S. Griggs, Personal communication (May 1996).

[13] J. L. Gross, T. W. Tucker, Topological Graph Theory, Wiley, New York, 1987.

[14] P. R. Hafner, Large Cayley graphs and digraphs with small degree and diameter, Computational Algebra and Number Theory (W. Bosma and van der Poorten, Eds.) Kluwer, Amsterdam (1995) 291-302.

[15] A. J. Hoffman, R. R. Singleton, On Moore graphs with diameter 2 and 3, IBM J. Res. Develop. 4 (1960) 497-504.

[16] M. N. Huxley, On the difference between consecutive primes, Invent. Math. 15 (1972) 164-170.

[17] B. D. McKay, nauty User’s Guide (Version 1.5), Technical Report TR-CS-90-02, Department of Computer Science, Australian National University, Canberra, 1990.