2022/10/27 by Ademir Hujdurović, Hujdurović, Ademir, Mitrović, Đorđe
Biochemistry, Genetics and Molecular Biology · Computer Science · #05C25 #Advanced Graph Theory Research #Biochemical Acid Research Studies #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2210.15249
openalex publication_date 2022/10/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph X is said to be unstable if the direct product X× K2 (also called the canonical double cover of X) has automorphisms that do not come from automorphisms of its factors X and K2. 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.