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$, $\mathrm{Aut}(\Gamma \times K_2)$ is not isomorphic to $\mathrm{Aut}(\Gamma) \times \mathbb{Z}_2$. We show that a connected and non-bipartite Cayley graph $\mathrm{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$ satisfying certain properties. The S-rings with these properties are characterized if $H$ is a cyclic group of twice odd order. As an application, a necessary and sufficient condition is 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$.