McKay–Miller–Širáň graph

In graph theory, the McKay–Miller–Širáň graphs are an infinite class of vertex-transitive graphs with diameter two, and with a large number of vertices relative to their diameter and degree. They are named after Brendan McKay, Mirka Miller, and Jozef Širáň, who first constructed them using voltage graphs in 1998.

Background

The context for the construction of these graphs is the degree diameter problem in graph theory, which seeks the largest possible graph for each combination of degree and diameter. For graphs of diameter two, every vertex can be reached in two steps from an arbitrary starting vertex, and if the degree is $d$ then at most $d$ vertices can be reached in one step and another $d(d-1)$ in two steps, giving the Moore bound that the total number of vertices can be at most $d^{2}+1$. However, only four graphs are known to reach this bound: a single edge (degree one), a 5-vertex cycle graph (degree two), the Petersen graph (degree three), and the Hoffman–Singleton graph (degree seven). Only one more of these Moore graphs can exist, with degree 57. For all other degrees, the maximum number of vertices in a diameter-two graph must be smaller. Until the construction of the McKay–Miller–Širáň graphs, the only known construction achieved a number of vertices equal to

$\left\lfloor {\frac {d+2}{2}}\right\rfloor \cdot \left\lceil {\frac {d+2}{2}}\right\rceil ,$

using a Cayley graph construction.

The McKay–Miller–Širáň graphs, instead, have a number of vertices equal to

${\frac {8}{9}}\left(d+{\frac {1}{2}}\right)^{2},$

for infinitely many values of $d$. The degrees $d$ for which their construction works are the ones for which $(2d+1)/3$ is a prime power and is congruent to 1 modulo 4. These possible degrees are the numbers

7, 13, 19, 25, 37, 43, 55, 61, 73, 79, 91, ...

The first number in this sequence, 7, is the degree of the Hoffman–Singleton graph, and the McKay–Miller–Širáň graph of degree seven is the Hoffman–Singleton graph. The same construction can also be applied to degrees $d$ for which $(2d+1)/3$ is a prime power but is 0 or −1 mod 4. In these cases, it still produces a graph with the same formulas for its size, diameter, and degree, but these graphs are not in general vertex-transitive.

Subsequent to the construction of the McKay–Miller–Širáň graphs, other graphs with an even larger number of vertices, $O(d^{3/2})$ fewer than the Moore bound, were constructed. However, these cover a significantly more restricted set of degrees than the McKay–Miller–Širáň graphs.

Constructions

The original construction of McKay, Miller, and Širáň, used the voltage graph method to construct them as a covering graph of the graph $K_{q,q}^{*}$, where $q=(2d+1)/3$ is a prime power and where $K_{q,q}^{*}$ is formed from a complete bipartite graph $K_{q,q}$ by attaching $(q-1)/4$ self-loops to each vertex. Instead, Šiagiová (2001) again uses the voltage graph method, but applied to a simpler graph, a dipole graph with $q$ parallel edges modified in the same way by attaching the same number of self-loops to each vertex.

It is also possible to construct the McKay–Miller–Širáň graphs by modifying the Levi graph of an affine plane over the field of order $q$.

Additional properties

The spectrum of a McKay–Miller–Širáň graph has at most five distinct eigenvalues. In some of these graphs, all of these values are integers, so that the graph is an integral graph.