Existence of non-Cayley Haar graphs

DOI10.1016/J.EJC.2020.103146MaRDI QIDQ2198980zbMATH OpenOpenAlexFDO

Authors István Kovács, Jie Wang, Yan-Quan Feng, Da-Wei Yang

Publication date 15 September 2020

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.04551

zbMATH Keywords

Cayley graphdihedral groupgeneralized dihedral groupHaar graph

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25)

Abstract: A Cayley graph of a group $H$ is a finite simple graph $Gamma$ such that its automorphism group $mAut(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 $mAut(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}imesmathbb{Z}_2$. This answers an open problem proposed by Est'elyi and Pisanski in 2016.

Recommendations

• On constructing normal and non-normal Cayley graphs
• On Cayley digraphs that do not have Hamiltonian paths
• scientific article; zbMATH DE number 1744089
• Cayley graphs
• scientific article; zbMATH DE number 2149408
• scientific article; zbMATH DE number 1827733
• On Cayley sum graphs of non-abelian groups
• On extendability of Cayley graphs
• On groups all of whose Haar graphs are Cayley graphs

Cites work

• A classification of pentavalent arc-transitive bicirculants
• A classification of the graphical \(m\)-semiregular representation of finite groups
• Cayley numbers with arbitrarily many distinct prime factors
• Cubic bi-Cayley graphs over abelian groups
• Cyclic Haar graphs
• Every finite group has a normal bi-Cayley graph
• Graphical Regular Representations of Non-Abelian Groups, I
• Graphical Regular Representations of Non-Abelian Groups, II
• scientific article; zbMATH DE number 3849262 (Why is no real title available?)
• scientific article; zbMATH DE number 3933295 (Why is no real title available?)
• scientific article; zbMATH DE number 3747160 (Why is no real title available?)
• scientific article; zbMATH DE number 3621981 (Why is no real title available?)
• scientific article; zbMATH DE number 3641459 (Why is no real title available?)
• scientific article; zbMATH DE number 3305184 (Why is no real title available?)
• scientific article; zbMATH DE number 3328108 (Why is no real title available?)
• Isomorphic tetravalent cyclic Haar graphs
• On graphical representations of cyclic extensions of groups
• On normality of n-Cayley graphs
• On semisymmetric cubic graphs of order \(6p^{2}\)
• On the action of non-Abelian groups on graphs
• Partial sum quadruples and bi-abelian digraphs
• Schur norms of bicirculant matrices
• Semisymmetric cubic graphs constructed from bi-Cayley graphs of A_n.
• Square-free non-Cayley numbers. On vertex-transitive non-Cayley graphs of square-free order.
• Tetravalent vertex-transitive graphs of order 4p
• The automorphisms of bi-Cayley graphs
• The Magma algebra system. I: The user language
• Vertex-transitive Haar graphs that are not Cayley graphs
• Which Haar graphs are Cayley graphs?

Cited in

(9)

• Vertex-transitive Haar graphs that are not Cayley graphs
• Cayley graph for the non-abelian tensor square of some finite groups
• On groups all of whose Haar graphs are Cayley graphs
• Which Haar graphs are Cayley graphs?
• On automorphisms of Haar graphs of abelian groups
• On the non-existence of Abelian Moore Cayley graphs with excess one
• Symmetries of the honeycomb toroidal graphs
• The existence of m-Haar graphical representations
• Haar graphical representations of finite groups and an application to poset representations

Describes a project that uses

Uses Software

• Magma

This page was built for publication: Existence of non-Cayley Haar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2198980)