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

设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)■Nu]∪Nv]}.利用插点方法,证明了如下结果:设G是k-连通图(k2),b是整数,0min {k,(2b-1+k)/2}(n(Y)-1),则G是哈密尔顿图.同时给出图是1-哈密尔顿的和哈密尔顿连通的相关结果.

Hamiltonicity and the Independent Sets of Partially Square Graphs

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 0min{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.