南京师大学报（自然科学版）2006，Vol.29Issue(2)：6-11,6.
哈密尔顿性和部分平方图的独立集
Hamiltonicity and the Independent Sets of Partially Square Graphs
摘要
Abstract
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}｜.关键词
哈密尔顿性/插点/独立集/部分平方图Key words
hamiltonicity/vertex insertion/independent set/partially square graph分类
数理科学引用本文复制引用
徐新萍..哈密尔顿性和部分平方图的独立集[J].南京师大学报（自然科学版）,2006,29(2):6-11,6.基金项目
Supported by the National Natural Science Foundation of China (10371055,10471037). （10371055,10471037）
