Which Haar graphs are Cayley graphs?

István Estélyi¹ ; Tomaž Pisanski²

¹FMF, University of Ljubljana, Jadranska 19, 1000 Ljubljana, Slovenia IAM, University of Primorska, Muzejski trg 2, 6000 Koper, Slovenia
²FAMNIT, University of Primorska, Glagoljaška 8, 6000 Koper, Slovenia FMF, University of Ljubljana, Jadranska 19, 1000 Ljubljana, Slovenia IAM, University of Primorska, Muzejski trg 2, 6000 Koper, Slovenia

The electronic journal of combinatorics, Tome 23 (2016) no. 3

Résumé

For a finite group $G$ and subset $S$ of $G,$ the Haar graph $H(G,S)$ is a bipartite regular graph, defined as a regular $G$-cover of a dipole with $|S|$ parallel arcs labelled by elements of $S$. If $G$ is an abelian group, then $H(G,S)$ is well-known to be a Cayley graph; however, there are examples of non-abelian groups $G$ and subsets $S$ when this is not the case. In this paper we address the problem of classifying finite non-abelian groups $G$ with the property that every Haar graph $H(G,S)$ is a Cayley graph. An equivalent condition for $H(G,S)$ to be a Cayley graph of a group containing $G$ is derived in terms of $G, S$ and $\mathrm{Aut } G$. It is also shown that the dihedral groups, which are solutions to the above problem, are $\mathbb{Z}_2^2,D_3,D_4$ and $D_{5}$.

Détail

DOI : 10.37236/5240

Classification : 05C25
Mots-clés : Haar graph, Cayley graph, dihedral group, generalized dihedral group