Journal article

Stability of graph p airs

Yan-Li Qin, Binzhou Xia, Jin-Xin Zhou, Sanming Zhou

JOURNAL OF COMBINATORIAL THEORY SERIES B | ACADEMIC PRESS INC ELSEVIER SCIENCE | Published : 2021

Abstract

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 grap..

View full abstract

Grants

Awarded by National Natural Science Foundation of China


Awarded by Fundamental Research Funds for Beijing Universities


Funding Acknowledgements

We are grateful to the anonymous referees for their helpful comments and Dr Jiyong Chen for his valuable advices. Part of the work was done during a visit of the first author to The University of Melbourne. The first author would like to thank The University of Melbourne for its hospitality during her visit and Beijing Jiaotong University for its financial support. She also thanks the National Natural Science Foundation of China (11671030) for its financial support during her PhD. The first author was supported by the Fundamental Research Funds for Beijing Universities allocated to Capital University of Economics and Business (XRZ2020058). The third author was supported by the National Natural Science Foundation of China (11671030, 12071023).