顶点距离大于2的局部化条件与ham iltonian图  

Localized Conditions with d_L{(x,y)}2 for R Hamiltonian Graphs

作　　者：毛林繁[1] 刘峰[2] 

机构地区：[1]北方交通大学理学院应用数学所,北京100044 [2]北京信息职业技术学院

出　　处：《河南师范大学学报（自然科学版）》2003年第1期17-21,共5页Journal of Henan Normal University(Natural Science Edition)

摘　　要：对任意正整数 i,若图 G的导出子图 L的顶点满足 : x,y∈ V(L ) ,d L(x,y) =i m ax{ d G(x) ,d G(y) } |G|/ 2 ,则称 L具有性质 DL(i) .设 C(G)为图 G的闭包 ,本文证明了下述结果 :任意一个 C(G) =G且边连通度≥3的 2 -连通图 ,若存在正整数 s使得 G中的导出子图 L满足 :(i) L K1 .3 有性质 DL(2 ) ;(ii)任意正整数 i,1 i s,L Bi 有性质 DL(i) ;(iii) L Zs+ 2 有性质 DL(s+2 ) ,则 G为 hamiltonian图 .由此得到 :每个边连通度≥ 3的 2 -连通 { K1 .3;Bi,1 i s} - f ree图 ,若 C(G) =G且 max{ d G(x) ,d G(y)对任意导出子图 L Zs+ 2 ,d L(x,y) =s+2 } |G|/ 2 ,则 G一定是 hamiltonian图 .从而For an integer i and an induced subgraph L of graph G, if x,y∈V(L),d L(x,y)=imax{d G(x),d G(y)}|G|/2,then L is called possessing the property D L(i). Let C(G) be the closure of the graph G. The following result is obtained in this paper: For any 2-connected graph with C(G)=G and λ(G)3, if there exists an integer s such that each induced subgraph L satisfying: (i) L possesses D L(2) if LK 1.3; (ii) For any integer i,1is,L possesses D L(i) if LB i; (iii) L possesses D L(s+2) if LZ s+2, then G is hamiltonian. As a by-product, we get that every 2-connected {K 1.3;B i,11s}-free graph with C(G)=G,λ(G)3 and max{d G(x),d G(y)| For any induced subgraph LZ s+2, d L(x,y)=s+2|G|/2 is hamiltonian.

关 键 词：顶点距离 局部化条件 HAMILTONIAN图 性质DL(κ) 导出子图 最长圈 连通图 

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