Some conditions implying stability of graphs

Abstract

A graph $X$ is said to be unstable if the direct product $X\times K_2$ (also called the canonical double cover of $X$) has automorphisms that do not come from automorphisms of its factors $X$ and $K_2$. It is non-trivially unstable if it is unstable, connected, non-bipartite, and distinct vertices have distinct sets of neighbours. In this paper, we prove two sufficient conditions for stability of graphs in which every edge lies on a triangle, revising an incorrect claim of Surowski and filling in some gaps in the proof of another one. We also consider triangle-free graphs, and prove that there are no non-trivially unstable triangle-free graphs of diameter 2. An interesting construction of non-trivially unstable graphs is given and several open problems are posed.

13 pages

Cited by in corpus (1)

• Stability of Cayley graphs and Schur rings