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 $(Gamma,Sigma)$ is stable if $Aut(GammatimesSigma) cong Aut(Gamma)times Aut(Sigma)$ and unstable otherwise, where $GammatimesSigma$ is the direct product of $Gamma$ and $Sigma$. An unstable graph pair $(Gamma,Sigma)$ is said to be a nontrivially unstable graph pair if $Gamma$ and $Sigma$ are connected coprime graphs, at least one of them is non-bipartite, and each of them has the property that different vertices have distinct neighbourhoods. We obtain necessary conditions for a pair of graphs to be stable. We also give a characterization of a pair of graphs $(Gamma, Sigma)$ to be nontrivially unstable in the case when both graphs are connected and regular with coprime valencies and $Sigma$ is vertex-transitive. This characterization is given in terms of the $Sigma$-automorphisms of $Gamma$, which are a new concept introduced in this paper as a generalization of both automorphisms and two-fold automorphisms of a graph.
تحميل البحث