Existence of non-Cayley Haar graphs

2019/08/13 by Feng, Yan-Quan, Kovács, István, Wang, Jie +1
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1908.04551

Abstract

A Cayley graph of a group H is a finite simple graph Γ such that its automorphism group \rm Aut(Γ) contains a subgroup isomorphic to H acting regularly on V(Γ), while a Haar graph of H is a finite simple bipartite graph Σ such that \rm Aut(Σ) contains a subgroup isomorphic to H acting semiregularly on V(Σ) and the H-orbits are equal to the partite sets of Σ. 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₆, D₈, D₁₀, the quaternion group Q₈ and the group Q₈×ℤ₂. This answers an open problem proposed by Estélyi and Pisanski in 2016.

Related

• On groups all of whose Haar graphs are Cayley graphs
• Which Haar graphs are Cayley graphs?
• Asymptotic enumeration of Haar graphical representations
• Two families of graphs that are Cayley on nonisomorphic groups
• Cayley graphs on non-isomorphic groups