行数为2的变换图的直径和距离性质

The Diameter and Distance-related Properties of Interchange Graph with Row Number Being 2

著名的图论专家Richard A.Brualdi于1980年提出了关于变换图G(R,S)直径的Brualdi猜想,但至今仍悬而未决。变换图的距离性质已在组合矩阵论、网络流理论等领域中得到了广泛的应用。基于对行数为2的变换图G(R*,S*)的基础结构性质的研究,得出变换图的距离和结构性质,G(R*,S*)的直径为r,对于G(R*,S*)中任意两个距离为k的点,存在k~2条内部不交的最短路联结这两个点。

Richard A.Brualdi, a famous expert of graph theory, raised the Brualdi’s Conjecture about the diameter of the interchange graphG(R,S) in 1980, which still remains open now. The distance properties of interchange graph has been widely used in the fields of combinatorial matrix theory and network flow theory. Based on the research on the basic structure properties of the interchange graph with row number being 2, the distance and structure properties are given. Two vertices are joined by k~2 internally-disjoint shortest paths provided the distance of any two vertices is k.The diameter ofG(R*,S*)is r.