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

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

作　　者：刘燕[1] 王江鲁[1] 

机构地区：[1]山东师范大学数学科学学院,山东济南250014

出　　处：《山东科学》2011年第6期5-7,共3页Shandong Science

摘　　要：如果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.

关 键 词：强[s t]-图 HAMILTON路 K-连通图 

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