本质集和1-几乎Hamilton性

Almost 1-Hamiltonicity and the Essential Independent Sets

设G是图 ,图G的独立集Z称为本质的 (简称本质集 ) ,如果存在 {z1 ,z2 } Z ,使得dist(z1 ,z2 ) =2 (这里dist(v,z)表示v与z间的距离 ) .结合插点方法以及 ∑ki=1N(Yi)和n(Y) (其中Y ={y1 ,y2 ,… ,yk}为G中任一独立集 ,Yi={yi,yi- 1 ,…yi- (b- 1 ) } Y ,i=1 ,2 ,…k,yi 的下标取模k,b(0 <b ≤k)为一正整数 ,n(Y)={v∈V(G) :dist(v ,Y) ≤ 2 } ) ,给出一个图是 1

Let G be a graph.An independent set Z in G is called an essential independnet set,if there are z 1 and z 2 in Z such that distance of z 1 and z 2 is equal to 2.In this paper,we use the technique of the vertex insertion on ( k+1 )?connected graphs to provide a proof for G to be almost 1 hamiltonian.The sufficient conditions are expressed by ∑ki=1N(Y i) and n(Y) in G for each independent set Y=｛y 1,y 2…y k｝ in G * ,where Y i=｛y i,y i 1 ,…,y i (b 1) ｝Y for i∈｛1,2,…,k｝ (the subscriptions of y′ j s will be taken modulo k ), b(0<b<k) is an integer,and n(Y)=｛v∈V(G) :dist (v,Y)≤2｝ .