图的路连通问题  

PATH CONNECTIVITY PROBLEMS

作　　者：蔡茂诚[1] 

机构地区：[1]中国科学院系统科学研究所

出　　处：《曲阜师范大学学报（自然科学版）》1994年第3期9-13,共5页Journal of Qufu Normal University(Natural Science)

基　　金：国家自然科学基金

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

关 键 词：图 路连通 哈密顿连通 泛连通 

分 类 号：O157.5[理学—数学]