Stability of Cayley graphs and Schur rings

Abstract

A graph $\Gamma$ is said to be unstable if for the direct product $\Gamma \times K_2$, $Aut(\Gamma \times K_2)$ is not isomorphic to $Aut(\Gamma )\times {\mathbb{Z}}_2$. In this paper we show that a connected and non-bipartite Cayley graph $Cay(H,S)$ is unstable if and only if the set $S\times \{1\}$ belongs to a Schur ring over the group $H\times {\mathbb{Z}}_2$ having certain properties. The Schur rings with these properties are characterized if $H$ is an abelian group of odd order or a cyclic group of twice odd order. As an application, a short proof is given for the result of Witte Morris stating that every connected unstable Cayley graph on an abelian group of odd order has twins (Electron.~J.~Combin, 2021). As another application, sufficient and necessary conditions are given for a connected and non-bipartite circulant graph of order $2p^e$ to be unstable, where $p$ is an odd prime and $e\ge 1$.

References in corpus (4)

• Canonical double covers of circulants
• On automorphisms of the double cover of a circulant graph
• Some conditions implying stability of graphs
• Automorphisms of the canonical double cover of a toroidal grid