极邻域并条件的哈密顿性

赵克文

琼州大学数学系 海南省五指山市  572200

摘要：考察极邻域并条件，得到：若2连通n阶图G的距离是2的任意两点x、y均有2|N(x)∪N(y)|+d(x)+d(y)≥2n-1,则G是哈密顿图。这是一个意想不到的结果。因为Faudree校长等1987年的结果是不相邻的|N(x)∪N(y)|≥(2n-3)/3,则G是哈密顿图；但1989年Lindquerster得到距离是2的|N(x)∪N(y)|≥(2n-3)/3,则G并不都是哈密顿图。而我们的这推广定理是类似L推广F的，那本应G并不一定都是哈密顿图。然而，我们竟然得到G必定是哈密顿图！那又是什么因素在起着改变这结构的作用呢？再附注一点：这推广定理的证明确实非常难--因从下面看本证明的关键是估计d(x)和d(y)的值，而“不相邻”时是非常容易考察的、即因起着限制作用的不相邻点较多，但“距离是2”时它的证明不象L推广F的那么单纯即量的关系少而是需要很多间接的关系才找到“似乎”的作用，但常顾此失彼非常头痛

关键词：哈密尔顿图；极邻域并条件

中图分类号：0157.5 MS（2000）分类号：05C38；05C45。

记N_G1(u)={v ∈V(G₁)：uv∈E(G)}。N_G1(H)=∪_u∈V(H)N_G1(u),N_G(u)可简记为N（u），N[u]=N(u)∪{u}，图G长为m的圈标记为C_m：x₁x₂…x_mx₁, N⁺c_m(u)={x_i+1：x_i∈Nc_m(u)} ,N^-c_m(u)={x_i-1：x_i∈Nc_m(u)},N^±c_m(u)= N⁺c_m(u)∪N^-c_m(u)。d(maxH)=max{d(x): x∈V(H)}，d(maxC_m⁺)=max{d(x_i): x_i∈N⁺_Cm(H)}和d(min C_m⁺)= min{d(x_i): x_i∈N⁺_Cm(H)},我们可类似定义反方向的图G的d(maxC_m^-)和d(min C_m^-)。邻域并NC=min{|N(x)∪N(y)|：x,y∈V(G),xy∈E(G)}。其它定义、记号参见文[5]。

本文：考察极邻域并条件，并证明下面结果：

定理：若2连通n阶图G的距离是2的任意两点x、y均有2|N(x)∪N(y)|+d(x)+d(y)≥2n-1,则G是哈密顿图。

证明：记C_m:x₁x₂…x_mx₁为G的一个最长圈，H为G-C_m的一分支，x∈V(H),x_i,x_j∈N_Cm(H)且{x_i+1,x_i+2,…x_j-1}∩N_Cm(H)=Ф, 记H中一条两端点分别和x_i和x_j相邻的路为P，则当x_h∈{x_i+1,x_i+2,…x_j}\{x_j、x_j-1}和x_j+1相邻时，则x_h+1和x_i+1、x均不相邻(因若x_h+1和x_i+1相邻，则有圈C*:x_iPx_jx_j-1…x_h+1x_i+1x_i+2…x_hx_j+1x_j+2…x_i比C_m长，矛盾； x_h+1和x相邻，类似有更长圈)；当x_h∈{x_j+1,x_j+2,…x_i}和x_j+1相邻时，则x_h-1和x_i+1、x均不相邻(因若x_h-1和x_i+1相邻，则有圈C*:x_iPx_jx_j-1…x_i+1x_h-1x_h-2…x_j+1x_hx_h+1…x_i比C_m长,矛盾);当y∈V(G-C_m) 和x_j+1相邻时，y和x_i+1、x不相邻（否则，类似有更长的圈）。从而易计算有d(x_i+1)≤n-(d(x_j+1)-|{x_j}|-|{x_i+1}|-|V(H)|,有d(x_i+1)+d(x_j+1)≤n-|V(H)|,记x∈V(H)，类似也有|N(x_i+1)∪N(x)|≤n-(d(x_j+1)-|{x_j-1,x_j}|-|{x_i+1,x}≤n-d(x_j+1).类似也有|N(x_i+1)∪N(x_j+1)|≤n-N⁺_Cm(H)-|V(H)|≤n- N⁺_Cm(x)-| V(H)|.

情况1： d(maxH)≥d(min C⁺)或d(maxH)＜d(min C⁺)但d(maxC⁺)＞ d(min C⁺)。

此时，若有d(maxH)≥d(min C⁺)，则不妨认为x∈V(H),d(x)=d(maxH)，和将存在x_i,x_j∈N_Cm(H)且{x_i+1,x_i+2,…x_j-1}∩N_Cm(H)=Ф, 使d(x)≥d(x_i+1)。其后如果（I）:d(x_j+1)＞d(x)，类似上面的推导有|N(x_i+1)∪N(x)|≤n-d(x_j+1)≤n-（d(x)+1）和|N(x_i+1)∪N(x)|≤n-d(x_j+1)≤n-（d(x_i+1)+1），有2|N(x_i+1)∪N(x)| +d(x)+d(x_i+1)≤2n-2，矛盾。如果（II）: d(x_j+1) ≤d(x)，类似上面的推导有|N(x_i+1)∪N(x_j+1)| ≤n-N⁺_Cm(x)-|V(H)|≤n-d(x)-|{x}|≤n- d(x_j+1)-1, 类似有2|N(x_i+1)∪N(x_j+1)| +d(x_j+1)+d(x_i+1)≤2n-2，矛盾。

若d(maxH)＜d(min C⁺)但d(maxC⁺)＞d(minC⁺)。则记x∈V(H)，不妨认为x_i,x_j∈N_Cm(H)且{x_i+1,x_i+2,…x_j-1}∩N_Cm(H)=Ф, d(x_j+1)＞d(x_i+1)，类似有|N(x_i+1)∪N(x)| ≤n-d(x_j+1)≤n-(d(x)+1)和|N(x_i+1)∪N(x)|≤n-d(x_j+1)≤n-(d(x_i+1)+1），有2|N(x_i+1)∪N(x)|+d(x)+d(x_i+1)≤2n-2，矛盾。

类似地，若d(maxH)≥d(min C^-)或d(maxH)＜d(min C^-)但d(maxC^-)＞ d(min C^-)。也矛盾。

情况2：d(maxH)＜d(min C⁺)且d(maxC⁺)=d(min C⁺)。

我们分情况讨论如下：

子情况2.1：| N_Cm(H)|≥3。

此时，记x_i,x_j,x_h∈N_Cm(H)且{x_i+1,x_i+2,…x_j-1,x_j+1,…x_h-1}∩N_Cm(H)=Ф,显然，若x_h+2和x_j+1相邻，记H中一条两端点分别和x_h和x_j相邻的路为P，则有圈C*:x_jPx_hx_h-1…x_j+1x_h+2x_h+3…x_j，若P不是一点，将有比C_m长的圈，矛盾。若P是一点，C*的点P∈N^±_Cm(H*),这将是情况1。所以x_h+2和x_j+1不相邻，此时也有x_h+1和x_i+1不相邻，记x∈V(H)，类似上面的推导有|N(x_i+1)∪N(x)| ≤n- d(x_j+1)-|{x_h+1}|=n-d(x_i+1)-1和|N(x_i+1)∪N(x)| ≤n- d(x)-1，有2|N(x_i+1)∪N(x)| +d(x)+d(x_i+1) ≤2n -2，矛盾。

子情况2.2：| N_Cm(H)|=2。

此时，我们断言1：导出子图G[H]是完全子图。否则，记x,y为H中不相邻的两点，有|N(x)∪N(y)| ≤n-(d(x_i+1)-|{x_i,x_j}|)-|{x_i+1,x_j+1}|≤n-d(x_i+1) ≤n-d(x)-1, 类似有2|N(x)∪N(y)| +d(x)+d(y) ≤2n -2，矛盾。断言2:H的每一点都和x_i,x_j均相邻。否则，若H中有x和x_j不相邻，类似有|N(x_i+1)∪N(x)| ≤n- (d(x_j+1)-|{x_j}|-|{x_i+1,x}≤n- d(x_j+1)-1，将有2|N(x_i+1)∪N(x)| +d(x)+d(x_i+1) ≤2n -2，矛盾。

子情况2.2.1：|V(H)| ≥2.

记 x_i,x_j∈N_Cm(H), |V(H)|=h,（I）：若有x_k∈{x_j+1,x_j+2,…x_i}和x_j+1相邻，也有x_k-r∈{x_j+1,x_j+2,…x_i}和x_i+1相邻(r是自然数),则显然{x_k-h,x_k-h+1,…x_k-1}中点和x_i+1均不相邻（否则在断言下易有更长的圈）,从而类似有|N(x_i+1)∪N(x)| ≤n-(d(x_j+1)-|{x_j-1,x_j}|-|{x_i+1,x}|-(|V(H)|-1)≤n- d(x_j+1)-1, 将有2|N(x_i+1)∪N(x)| +d(x)+d(x_i+1) ≤2n-2，矛盾。同样若x_h∈{x_i+1,x_i+2,…x_j-1}和x_j+1相邻时，也有x_h+r和x_i+1相邻时,也有矛盾。（II）：若当x_k∈{x_j+1,x_j+2,…x_i}和x_j+1相邻，则{x_j,x_j+1,…x_k-1}中点和x_i+1均不相邻；若当x_h∈{x_i+1,x_i+2,…x_j-1}和x_j+1相邻时，则{x_h+1,x_h+2,…x_j}中点和x_i+1均不相邻。此时，将有当x_k∈{x_j,x_j+1,…x_i}和x_j+1相邻时，则{x_j,x_j+1,…x_k-1}中每点和x_j+1均也相邻；当x_h∈{x_i+1,x_i+2,…x_j-1}和x_j+1相邻时，则{x_h+1,x_h+2,…x_j}中点和x_j+1均也相邻（否则将易有|N(x_i+1)∪N(x)| ≤n- d(x_j+1)-1, 则2|N(x_i+1)∪N(x)| +d(x)+d(x_i+1) ≤2n -2，矛盾），此时，记x_h∈{x_i+1,x_i+2,…x_j-1}满足x_h和x_i-1不相邻，而x_h-1和x_i-1相邻（这情况存在，因x_i和x_i-1相邻），其后，当x_k∈{x_i+1,x_i+2,…x_j-1}和x_j+1相邻时，x_k+1和x_h不相邻（否则有更长的圈）；当x_k∈{x_j,x_j+1,…x_i}和x_j+1相邻时，x_k-1和x_h不相邻,又x_h和x_i-1不相邻，类似有|N(x_i+1)∪N(x_h)| ≤n- (d(x_j+1)-|{x_j-1,x_j }|-|{x_i-1,x_h,x}|≤n-d(x_j+1)-1, 则2|N(x_i+1)∪N(x_h)| +d(x)+d(x_i+1) ≤2n-2，矛盾。

子情况2.2.2：|V(H)|=1.

记V(H)= {x}，显然d(x_i+1)≤n-(d(x_j+1)-|{x_j}|-|{x_i+1}|-|V(H)|,有d(x_i+1)≤n-d(x_j+1)-1，由情况2知有3≤d(x)+1≤d(x_i+1)=d(x_j+1)≤(n-1)/2,易有n≥9，将有2|N(x_i+1)∪N(x)| +d(x)+d(x_i+1) ≤2n-2，矛盾。#

参考文献

1、Chen GT, One sufficient condition for Hamiltonian graphs, J.Graph Theory,1990,14:501-508.

2、Ore.O, Note on Hamiltonian circuits, Amer.Math.Monthly 1960,67:55.

3、Faudree RJ, Gould RJ, Jacobson MS, Schelp RH, Neighborhood unions and Hamiltonian properties in graphs, J.Combin.Theory B,1989,47:1-9.

4、Bauer D, Fan G.H and Veldman H.J, Hamiltonian propeties  of graphs  with large  neighborhood  unions. Discrete Math.,1991,96:33-49.

5、Gould RJ, Updating the Hamiltonian Problem - A Survey, Journal of Graph Theory 15 (1991), 121-157.