图的路连通问题

PATH CONNECTIVITY PROBLEMS

如果图Ｇ的每对不同顶点ｕ和ｖ之间都有哈密顿路相连，则称Ｇ是哈密顿连通的；而如果对于所有满足条件以ｄ（ｕ，ｖ）≤ｑ≤ｎ－１的整数ｑ，ｕ和ｖ之间有长为ｑ路相连，则和Ｇ是泛连通的，其中以ｄ（ｕ，ｖ）是ｕ和ｖ间的距离，而ｎ是Ｇ的顶点数。本文证明了下述两个结果：（１）２ｋ＋１个顶点的ｋ正则简单图是哈密顿连通的，（２）ｋ连通国中任何两顶点之间存在ｋ－１条长度不同的路；进而如果Ｇ的顶点数小于２ｋ，则Ｇ是泛连通的。

A graph G is Hamiltonian-connected if every pair of distinct vertices u and vare joined by a Hamiltonian path,and panconnected if u and v are joined by paths of alllengths q,for d(u,v)≤q≤n-1(where d(u,v)is the distance between u and v,and n is theorder of G).In this paper the following two results are proved:(1)A k-regular simple graphof order 2k+1 is Hamiltonian-connected.(2)In a k-connected graph G,between any two ver-tices there exist k-1 paths with different lengths.Furthermore,G is panconnected if its orderis less than 2k.