The McKay-Miller-Širáň graph 
is a regular graph with
vertices for each prime power 
. The family arose in the study of the degree-diameter
problem for graph diameter 2 (McKay et al.
1998, Li 2026).
The construction uses two copies of 
,
where 
is the finite field of order 
. The cross edges join 
in the first copy to 
in the second for 
. Within each copy, edges join vertices with
the same first coordinate whose second coordinates differ by an element of a symmetric
difference set. Write 
,
with 
, 0, or 1, and let 
generate the multiplicative
group of 
. For odd 
,
the difference sets are 
and 
,
where 
and 
for 
or 
for 
. For even 
they are 
and 
. The vertex
degree is 
. When 
, the graph is vertex-transitive
(Li 2026, §2). For example, 
is the Hoffman-Singleton
graph (McKay et al. 1998).
Li (2026, Theorem 1.2) constructed at least ![[(q-1)/2]](/images/equations/McKay-Miller-SiranGraph/Inline28.svg)
pairwise edge-disjoint Hamiltonian
cycles for every prime power 
, where ![[·]](/images/equations/McKay-Miller-SiranGraph/Inline30.svg)
is the ceiling function.
for Every Prime Power 
." 9 Nov 2026.