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

Hamiltonicity and the Independent Sets of Partially Square Graphs

作　　者：徐新萍[1] 

机构地区：[1]江苏教育学院数学系,江苏南京210013

出　　处：《南京师大学报（自然科学版）》2006年第2期6-11,共6页Journal of Nanjing Normal University(Natural Science Edition)

基　　金：SupportedbytheNationalNaturalScienceFoundationofChina(10371055,10471037)

摘　　要：设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}｜.

关 键 词：哈密尔顿性 插点 独立集 部分平方图 

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