摘要
讨论了邻集并下界为 n-δ(G)情形下图 G 的 Hamilton 连通性,证明了若对 G 中任意两个不相邻点 n 和 v,有|N(u)∪N(v)|≥n-δ,则除了两张图外,G 是 Hamilton 连通图.
This paper studies the Hamilton-connected properties of graph G when the low- er bound of the neighborhood unions is n-δ(G),proves that if for any pair of nonadjacent vertices u,v,|N(u)∪N(v)|≥n-δ,then G is Hamilton-connected unless G is one of the two spe- cial graphs.
关键词
连通图
路
邻集并
最小度
哈密顿连通图
Hamilton-connected graph
Path
Neighborhood union
Minimum degree
