哈密尔顿性和部分平方图的独立集  

Hamiltonicity and the Independent Sets of Partially Square Graphs

作　　者：徐新萍[1] 

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

出　　处：《数学的实践与认识》2009年第10期145-151,共7页Mathematics in Practice and Theory

基　　金：国家自然科学基金(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]}.利用插点方法,证明了如下结果:设G是k-连通图(k2),b是整数,0<b<k+1.若对于图G的部分平方图G*的任一独立集Y={y0,y1,…,yk},在G中有sum from i=1 to k ︱N(Yi)︱+b︱N(y0)︱>min {k,(2b-1+k)/2}(n(Y)-1),则G是哈密尔顿图.同时给出图是1-哈密尔顿的和哈密尔顿连通的相关结果.Let G be a graph, 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 to prove the following result： Let G be a k-connected graph with k ≥ 2;b an integer, and 0 〈 b 〈 k ＋ 1. If ∑（i=1→k）｜N（yi）｜＋b｜N（y0）｜〉min{k,2b-1＋k/2}（n（Y）-1） in G for eech Y = {y0,y1,…,yk} ∈ Ik＋1（G^＊）, then G is hamiltonian. In addition, the corresponding results on 1-hamiltonian or hamilton-connected are obtained, too.

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

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