Every finite group has a normal bi-Cayley graph

Abstract

A graph Γ with a group H of automorphisms acting semiregularly on the vertices with two orbits is called a bi-Cayley graph over H. When H is a normal subgroup of Aut(Γ), we say that Γ is normal with respect to H. In this paper, we show that every finite group has a connected normal bi-Cayley graph. This improves a theorem by Arezoomand and Taeri and provides a positive answer to a question reported in the literature.