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.
[1] 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
in two steps, giving the Moore bound that the total number of vertices can be at most
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.
[2] The McKay–Miller–Širáň graphs, instead, have a number of vertices equal to for infinitely many values of
is a prime power and is congruent to 1 modulo 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.
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
is formed from a complete bipartite graph
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
[3][5] The spectrum of a McKay–Miller–Širáň graph has at most five distinct eigenvalues.