哈密尔顿图的局部化临域并条件(英文)

New Localized Neighborhood Union Condition for Hamiltonian Graphs

采用图的局部化临域并条件 ,本文证明了下述结果 :设G是一个p阶 2 -连通图 ,Li- <G ,i=1,2 (L1≠L2或L1=L2 )且对任意顶点xi,yi∈V(Li) ,i=1,2和 {x1,y1}≠ {x2 ,y2 } ,dLi(xi,yi) =2 ,有下列不等式(D) 3|N(x1)∪N(y1) |+3|N(x2 )∪N(y2 ) |≥ 4p - 2 ,(1)若Li≌K1.3 或K1.3 +e ,i=1,2 ,则G为哈密尔顿图 .(2 )若Li≌K1.3 +e或P4 ,i=1,2 ,则除非G中有一个强D1-圈 ,G一定是哈密尔顿图t这一结果推广了Lindquester的结果 :每个p阶 2 -连通图G ,若有NC2≥ (2p - 1) /3,则一定是哈密尔顿图 .

Many localized conditions has been presented in recent years. Using the subgraphs pairs {K 1.3 ,K 1.3 +e} and {K 1.3 +e,P 4}, the following new localized result on hamiltonian graphs is obtained. Theorem. Let G be a 2-connected graph with order p,L i-< G, i=1,2 (L 1≠L 2 or L 1=L 2)and for any vertices x i,y i∈V(L i), i=1,2 and {x 1,y 1}≠{x 2,y 2}, d Li (x i,y i)=2,the following inequality holds (A) 3|N(x 1)∪N(y 1)|+3|N(x 2)∪N(y 2)|≥4p-2, then (i) if L i≌K 1.3 or K 1.3 +e, i=1,2, then G is hamiltonian. (ii) If L i≌K 1.3 +e or P 4,i=1,2, then G is hamiltonian unless G is dominated by a stronger D 1-cycle, especially, L(G) is hamiltonian. Now define NC 2 L=min{|N(x)∪N(y)|| L -< G, x,y∈V(G) and d Li (x,y)=2}. Corollary. Let G be a 2-connected graph with order p,L-< G and NC 2 L≥(2p-1)/3. Then (i) if L≌K 1.3 or K 1.3 +e, then G is hamiltonian. (ii)if L≌K 1.3 +e or P 4, then G is hamiltonian unless G is dominated by a stronger D 1-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.