2025/04/08 by Junyang Zhang, Zhang, Junyang
Computer Science · Engineering · Mathematics · #Advanced Differential Equations and Dynamical Systems #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Structural Analysis and Optimization
paper · pdf · doi:10.48550/arxiv.2504.05721
openalex publication_date 2025/04/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph Γ is said to be stable if Aut(Γ× K2)\congAut(Γ)× ℤ2 and unstable otherwise. If an unstable graph is connected, non-bipartite and any two of its distinct vertices have different neighbourhoods, then it is called nontrivially unstable. We establish conditions guaranteeing the instability of various graph products, including direct products, direct product bundles, Cartesian products, strong products, semi-strong products, and lexicographic products. Inspired by a condition for the instability of direct product bundles, we propose a new sufficient condition for circulant graphs to be unstable and refine existing instability conditions from the literature. Based on these results, we categorize unstable circulant graphs into two distinct types and further propose a classification framework.