关于图的泛连通性的几个结果

SOME RESULTS ON THE PANCONNECTITY OF GRAPHS

如果对ａ≤ｉ≤ｂ，图Ｇ的任一对顶点ｕ、ｖ都存在长为ｉ－１的路Ｐｉ（ｕ，ｖ），则称Ｇ是［ａｂ］－泛连通的．文中证明了关于图的泛连通性的下述结果：设Ｇ为ｎ阶连通图，且对Ｇ中任一对距离为２的顶点ｕ，ｖ，有ｄ（ｕ）＋ｄ（ｖ）≥ｎ，则图Ｇ是［５ｎ］－泛连通的当且仅当Ｇ是Ｈ连通的．此结果推广了Ｆａｕｄｒｅｅ和Ｓｃｈｅｌｐ的一个结论．

The graph G is called a [a b] -panconnected graph if the path p_i(u,v) of length i- 1exist for all pairs of venices u and v of G, where a≤i≤b. We get the following result on panconnectivity of graphs: let G be a connected graph of ordern,if d(u) +d(v) ≥n for all pairs of venices u and v that are at distance two, then the graph G is a [5 n] -panconneded graph if and only if G is a H-Connected graph. By using the result, we may get one of the results proved by Faudree and Schelp.