k-连通的强-[k+4,2]图的Hamilton路

Hamilton path of a k-connected strong-[k+4,2] graph

如果G的任意s个点的导出子图中至少含有t条独立边,则称图G为强-[s,t]图。本文证明了以下结果:设G是k-连通的强-[k+4,2]图,且δ≥k+1,则G或者有Hamilton路或者同构于(∪ki=+12 Hi)∨Gk,其中HiK2,i=1,2…k+2,Gk是含有k个点的任意图。

A graph G is a strong -E s, tl graph if there are at least t independent edges in every included subgraph of s vertices. This paper proves that if G is a k-connected strong -E k ＋ 4,21 graph with δ≥ k ＋ 1, then G has a Hamilton path or is isomorphic to （ Uk＋2i=1Hi） V Gk,where Hi=K2 ,i= 1,2...k＋2,and Gk is an arbitrary graph of k vertices.