Stability of graph pairs

• Published in: Journal of combinatorial theory. Series B 2021-03, Vol.147, p.71-95
• Main Authors: Qin, Yan-Li, Xia, Binzhou, Zhou, Jin-Xin, Zhou, Sanming
• Format: Article
• Language: English
• Subjects: Direct product of graphs; Stable graph; Stable graph pair
• ISSN: 0095-8956; 1096-0902
• DOI: 10.1016/j.jctb.2020.10.002

We start up the study of the stability of general graph pairs. This notion is a generalization of the concept of the stability of graphs. We say that a pair of graphs (Γ,Σ) is stable if Aut(Γ×Σ)≅Aut(Γ)×Aut(Σ) and unstable otherwise, where Γ×Σ is the direct product of Γ and Σ. An unstable graph pair (Γ,Σ) is said to be a nontrivially unstable graph pair if Γ and Σ are connected coprime graphs, at least one of them is non-bipartite, and each of them has the property that different vertices have distinct neighborhoods. We obtain necessary conditions for a pair of graphs to be stable. We also give a characterization of a pair of graphs (Γ,Σ) to be nontrivially unstable in the case when both graphs are connected and regular with coprime valencies and Σ is vertex-transitive. This characterization is given in terms of the Σ-automorphisms of Γ, which are a new concept introduced in this paper as a generalization of both automorphisms and two-fold automorphisms of a graph.