2024/03/02 by Wang, Xiaomeng, Xu, Shou-Jun, Zhou, Sanming
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2403.01220
A graph pair (Γ, Σ) is called stable if \aut(Γ)×\aut(Σ) is isomorphic to \aut(Γ×Σ) and unstable otherwise, where Γ×Σ is the direct product of Γ and Σ. A graph is called R-thin if distinct vertices have different neighbourhoods. Γ and Σ are said to be coprime if there is no nontrivial graph Δ such that Γ≅ Γ1 × Δ and Σ≅ Σ1 × Δ for some graphs Γ1 and Σ1. An unstable graph pair (Γ, Σ) is called nontrivially unstable if Γ and Σ are R-thin connected coprime graphs and at least one of them is non-bipartite. This paper contributes to the study of the stability of graph pairs with a focus on the case when Σ= Cn is a cycle. We give two sufficient conditions for (Γ, Cn) to be nontrivially unstable, where n ≠ 4 and Γ is an R-thin connected graph. In the case when Γ is an R-thin connected non-bipartite graph, we obtain the following results: (i) if (Γ, K2) is unstable, then (Γ, Cn) is unstable for every even integer n ≥ 4; (ii) if an even integer n ≥ 6 is compatible with Γ in some sense, then (Γ, Cn) is nontrivially unstable if and only if (Γ, K2) is unstable; (iii) if there is an even integer n ≥ 6 compatible with Γ such that (Γ, Cn) is nontrivially unstable, then (Γ, Cm) is unstable for all even integers m ≥ 6. We also prove that if Γ is an R-thin connected graph and n ≥ 3 is an odd integer compatible with Γ, then (Γ, Cn) is stable.