Existence of non-Cayley Haar graphs

Abstract

A Cayley graph of a group $H$ is a finite simple graph $\Gamma$ such that its automorphism group $\mathrm{Aut}(\Gamma )$ contains a subgroup isomorphic to $H$ acting regularly on $V(\Gamma )$, while a Haar graph of $H$ is a finite simple bipartite graph $\Sigma$ such that $\mathrm{Aut}(\Sigma )$ contains a subgroup isomorphic to $H$ acting semiregularly on $V(\Sigma )$ and the $H$-orbits are equal to the partite sets of $\Sigma$. It is well-known that every Haar graph of finite abelian groups is a Cayley graph. In this paper, we prove that every finite non-abelian group admits a non-Cayley Haar graph except the dihedral groups $D_6$, $D_8$, $D_{10}$, the quaternion group $Q_8$ and the group $Q_8\times {\mathbb{Z}}_2$. This answers an open problem proposed by Estélyi and Pisanski in 2016.