Stability of circulant graphs

摘要

The canonical double cover D(Gamma) of a graph r is the direct product of Gamma and K-2. If Aut(D(Gamma)) = Aut(Gamma) x Z(2) then Gamma is called stable; otherwise Gamma is called unstable. An unstable graph is nontrivially unstable if it is connected, non-bipartite and distinct vertices have different neighborhoods. In this paper we prove that every circulant graph of odd prime order is stable and there is no arc-transitive nontrivially unstable circulant graph. The latter answers a question of Wilson in 2008. We also give infinitely many counterexamples to a conjecture of Marusic, Scapellato and Zagaglia Salvi in 1989 by constructing a family of stable circulant graphs with compatible adjacency matrices. (C) 2018 Elsevier Inc. All rights reserved.