哈密尔顿图的局部化临域并条件

采用图的局部化临域并条件 ,本文证明了下述结果 :设G是一个p阶 2 -连通图 ,Li-

New Localized Neighborhood Union Condition for Hamiltonian Graphs

Many localized conditions has been presented in recent years. Using the subgraphs pairs {K1.3,K1.3+e} and {K1.3+e,P4}, the following new localized result on hamiltonian graphs is obtained.Theorem. Let G be a 2-connected graph with order p,Li-< G, i=1,2 (L1≠L2 or L1=L2)and for any vertices xi,yi∈V(Li), i=1,2 and {x1,y1}≠{x2,y2}, dLi(xi,yi)=2,the following inequality holds(A) 3|N(x1)∪N(y1)|+3|N(x2)∪N(y2)|≥4p-2,then(i) if Li≌K1.3 or K1.3+e, i=1,2, then G is hamiltonian.(ii) If Li≌K1.3+e or P4,i=1,2, then G is hamiltonian unless G is dominated by a stronger D1-cycle, especially, L(G) is hamiltonian.Now define NC2L=min{|N(x)∪N(y)|| L -< G, x,y∈V(G) and dLi(x,y)=2}.Corollary. Let G be a 2-connected graph with order p,L-< G and NC2L≥(2p-1)/3. Then(i) if L≌K1.3 or K1.3+e, then G is hamiltonian.(ii)if L≌K1.3+e or P4, then G is hamiltonian unless G is dominated by a stronger D1-cycle, especially, L(G) is hamiltonian.Clearly, this result generalizes Lindquester's result which asserts that for a 2-connected graph with order p, if NC2≥(2p-1)/3, then G is hamiltonian.