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  then at most  vertices can be reached in one step and another  in two steps, giving the Moore bound that the total number of vertices can be at most . 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

using a Cayley graph construction.

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

for infinitely many values of . The degrees  for which their construction works are the ones for which  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  for which  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,  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 , where  is a prime power and where  is formed from a complete bipartite graph  by attaching  self-loops to each vertex.
Instead,  again uses the voltage graph method, but applied to a simpler graph, a dipole graph with  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 .

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.

References

Parametric families of graphs
Regular graphs