2018/02/14 by Qin, Yan-Li, Xia, Binzhou, Zhou, Sanming · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1802.04921
The canonical double cover D(Γ) of a graph Γ is the direct product of Γ and K2. If Aut(D(Γ))=Aut(Γ)×ℤ2 then Γ is called stable; otherwise Γ 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 Marušič, Scapellato and Zagaglia Salvi in 1989 by constructing a family of stable circulant graphs with compatible adjacency matrices.