All McKay-Miller-Širáň graphs are bi-Cayley

Abstract

McKay, Miller, and Širáň (1998) introduced a family of graphs, denoted $H_q$ for prime powers $q>2$, of order $2q^2$, diameter $2$, and degree $(3q-\delta)/2$, where $q \equiv \delta \pmod 4$ with $\delta \in \{-1, 0, 1\}$. The McKay-Miller-Širáň (MMS) graphs are vertex-transitive for $q \in \{3,4\}$ and for every $q \equiv 1 \pmod 4$, with $H_3$ and $H_4$ being the only two Cayley graphs in the family. For other prime powers, the automorphism group of $H_q$ exhibits two vertex orbits.Originally, the MMS graphs were constructed as lifts of complete bipartite graphs $K_{q,q}$ with attached loops or semiedges. Later, Šiagiová (2001) showed that for $q \equiv 1 \pmod 4$, these graphs are bi-Cayley; that is, they are lifts of two-vertex graphs. Using Hafner's (2004) results on the automorphism groups of MMS graphs, we show that MMS graphs $H_q$ are bi-Cayley for \emph{every} prime power $q > 2$.