  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(\Gamma\times\Sigma) \cong
Aut(\Gamma)\times Aut(\Sigma)$ and unstable otherwise, where
$\Gamma\times\Sigma$ 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.
