Journal article
Stability of circulant graphs
YL Qin, B Xia, S Zhou
Journal of Combinatorial Theory Series B | ACADEMIC PRESS INC ELSEVIER SCIENCE | Published : 2019
Abstract
The canonical double cover D(Γ) of a graph Γ is the direct product of Γ and K 2 . If Aut(D(Γ))=Aut(Γ)×Z 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.
Grants
Awarded by National Natural Science Foundation of China
Funding Acknowledgements
This work was done during the first author's visit to The University of Melbourne. The first author would like to thank Beijing Jiaotong University for financial support for this visit and National Natural Science Foundation of China (11671030) for financial support during her PhD program. The first author is very grateful to Professor Jin-Xin Zhou for suggesting the research topic and would like to thank Professor Jin-Xin Zhou and Professor Yan-Quan Feng for helpful advices. The authors would like to thank the anonymous referees for their very valuable comments.