摘要
设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}|.
出处
《南京师大学报(自然科学版)》
CAS
CSCD
北大核心
2006年第2期6-11,共6页
Journal of Nanjing Normal University(Natural Science Edition)
基金
SupportedbytheNationalNaturalScienceFoundationofChina(10371055,10471037)
关键词
哈密尔顿性
插点
独立集
部分平方图
hamiltonicity, vertex insertion, independent set, partially square graph