哈密尔顿性和部分平方图的独立集(英文)

Hamiltonicity and the Independent Sets of Partially Square Graphs

设G是一个图,G的部分平方图G*满足V(G*)=V(G),E(G*)=E(G)∪{uv:uv∈E(G),且J(u,v)≠},这里J(u,v)={w∈N(u)∩N(v),N(w)N[u]∪N[v]}.本文利用插点方法,给出了关于k,或(k+1)-连通(k≥2)图G是哈密尔顿的,1-哈密尔顿的或哈密尔顿连k通的统一证明.其充分条件是在图G中关于∑i=1|N(Yi)|+b|N(y0)|与n(Y)的不等式,这里Y是图G的部分平方图G*的任一独立集,对于i∈{1,2,…,k},Yi={yi,yi-1,…,yi-(b-1)}Y(yj的下标将取模k);b是一个整数,且0<b<k+1;n(Y)=|{v∈V(G),dist(v,Y)≤2}|.

The partially square graph G ＊ of G is a graph satisfying V（ G ＊ ） = V（G） and E（ G ＊ ） = E（G） ∪ { uv： uv ∈E （ G）, and J（u,v） ≠ ф }. In this paper, we will use the technique of the vertex insertion on k or （ k ＋ 1 ） -connected （k≥2） graphs to provide a unified proof for G to be hamiltonian, 1-hamiltonian or hamiltonian-connected. The suffi cient conditions are expressed by the inequality concerning k∑i=1 ｜ N（ Yi ） ｜ ＋ b ｜ N（ y0 ） ｜ and n（Y） in G for independent sets Y={y0,y1,…,yk} inG^＊, whereb（0〈b〈k＋1） is an integer, Yi ={yi,yi-1,…,yi-（b-1）}（∪）Y／{yo} fori∈{ 1,2,…,k} （the subscriptions of y＇js will be taken modulo k）, and n（Y） =｜{v∈V（G）： dist（v,Y） ≤2}｜.