McKay–Miller–Širáň graph

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 ${\displaystyle d}$ then at most ${\displaystyle d}$ vertices can be reached in one step and another ${\displaystyle d(d-1)}$ in two steps, giving the Moore bound that the total number of vertices can be at most ${\displaystyle 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

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

using a Cayley graph construction.[2]

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

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

for infinitely many values of ${\displaystyle d}$. The degrees ${\displaystyle d}$ for which their construction works are the ones for which ${\displaystyle (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.[2] The same construction can also be applied to degrees ${\displaystyle d}$ for which ${\displaystyle (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.[1][3]

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

The original construction of McKay, Miller, and Širáň, used the voltage graph method to construct them as a covering graph of the graph ${\displaystyle K_{q,q}^{*}}$, where ${\displaystyle q=(2d+1)/3}$ is a prime power and where ${\displaystyle K_{q,q}^{*}}$ is formed from a complete bipartite graph ${\displaystyle K_{q,q}}$ by attaching ${\displaystyle (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 ${\displaystyle q}$ parallel edges modified in the same way by attaching the same number of self-loops to each vertex.[2]

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 ${\displaystyle q}$.[3][5]

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.[6]