2025/09/30 by Wang, Xiaomeng, Qin, Yan-Li, Xia, Binzhou
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2509.26170
A pair of graphs (Γ,Σ) is called unstable if their direct product Γ×Σ admits automorphisms not from Aut(Γ)\timesAut(Σ), and such automorphisms are said to be unexpected. The stability of a graph Γ refers to that of (Γ,K2). While the stability of individual graphs has been relatively well studied, much less is known for graph pairs. In this paper, we propose a conjecture that provides the best possible reduction of the stability of a graph pair to the stability of a single graph. We prove one direction of this conjecture and establish partial results for the converse. This enables the determination of the stability of a broad class of graph pairs, with complete results when one factor is a cycle.