点泛圈性的邻域并条件的最好结果

赵克文

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

摘要：1991年，哈密顿图的世界大师Faudree等提出点泛圈性猜想：“若2连通n阶图G，NC₂≥n-δ+1，则G是点泛圈图”。1995年，我们最先在《Aut.J. Combin.》宣告此猜想的证明。这里我们进一步考察NC₂≥n-δ的Cⁿ₅--点泛圈图。

关键词：点泛圈图；邻域并；圈

中图分类号：0157.5            MS（1991）分类号：05C38

1 引言

本文研究的图G=（V,E）均是简单图，图G的最小度用δ表示。让u是G 的一点，G₁是G的一个子图，则NG₁（u）={v ∈V(G₁)｜uv∈E(G)}。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)。图G的邻域并NC=min{|N(x) ∪N(y)|x,y∈V(G),xy∈E(G)}，2邻域并NC₂=min{|N(x) ∪N(y)|x,y∈V(G),d(x,y)=2}.

    称n阶图G是哈密尔顿（hamilton）图，如果G有长为n的圈C_n。称n阶图G是泛圈图，如果G有长为3至n的每个长度的圈。称n阶图G是Cⁿ_m—点泛圈图（m是大于2的整数，m≤n），如果G的每点有过它的长为m至n的每个长度的圈。Cⁿ₃—点泛圈图是点泛圈图。P_m－图是G的任两点均有以它们为端点的阶为m的路。称n阶图G是哈密尔顿连通图，如果G的每两点有(以它们为两端点)阶为n的路的圈(即G是P_n－图)。称n阶图G是Pⁿ_m--泛连通图，如果G的每两点有阶为m至n的每个整数的路(即G是P_r－图,r=m,m+1,…n)。

1987年，Faudree,Gould,Jacobson,Schelp等四个著名图论专家创立了“Neighborhood unions Conditions”(译为邻域并条件，即NC和NC₂)这个领域。和他们在文[8]中研究NC的2连通图，得到：若2连通n阶图G，NC≥m,则图G的最长圈的长度≥min{n，m+2}

1991年在文［1］中Faudree ,Gould ,Jacobson ,Lesnian等人并提出下面点泛圈图猜想：

猜想^[1]：若2连通n阶图G，NC≥n-δ+1，则G是点泛圈图。

本文中我们研究比猜想更深入的条件NC₂≥n-δ下的点泛圈图性，取得下面定理：

定理2：若2连通n(n≥6）阶图G，NC₂≥n-δ，则G是Cⁿ₅--点泛圈图或K_n/2，n/2。

2 引理和定理

引理2.1：若2连通n(n≥6）阶图G，NC₂≥n-δ，δ=2，则G的每点有过它的C₃和C₄或G∈K₁∨K^*₂:K_n-3。（这里图K₁∨K^*₂:K_n-3是K₁和K^*₂的联图及K^*₂的两个点和K_n-3中一些点相连形成的2连通图，K_s是s阶完全图，K^*₂只是2阶图）

证明：对G中任一点u。

1：对G中满足d（u）＞2的每点u。

此时，因NC₂≥n-δ，知N（u）有相邻的两点（若N（u）没有相邻的两点。则记x,y

为N（u）中两点, NC₂≤∣N（x）∪N(y)∣≤n-∣N（u）∣＜n-δ,矛盾＝。有过u的C₃。

1.1：若N（u）的导出子图有长为2的路。

    则有过u的C₃、C₄。

1.2：若N（u）的导出子图只有长为1的路。

记x₁，x₂，x₃为N（u）中三点且x₁和x₂相邻，因G是2连通，则G-N[u]中有点（记为y）和x₁，x₂之一(认为x₁)相邻。其后若y和x₂，x₃中至少一点相邻，则有过u的C₃、C₄。（若y和x₂，x₃均不相邻，则 NC₂≤∣N（x₂）∪N(x₃)∣≤n-∣{y，x₂，x₃}∣＜n-δ，矛盾）。

2：对G中满足d（u）＝2的每点u。

若有过u的C₃、C₄，则完成引理。若没有，由NC₂≥n-δ，易知G-N[u] 是完全子图（因为若G-N[u]有不相邻的两点x,y，则NC₂≤∣N（x）∪N(y)∣≤n-∣{x,y,u}∣=n-3≤n-δ-1,

矛盾）。则G∈K₁∨K^*₂:K_n-3。

引理2.2：若2连通n阶图G，NC₂≥n-δ，δ=3，则G的每点有过它的C₃、C₄或C₄、C₅或G=K_n/2,n/2或G∈K₁∨K¹₃:K_n-4（这里K¹₃是有且只有一条边的3阶图，K¹₃:K_n-4是K¹₃的3个点均和K_n-4中一些点相邻）。

证明：对任意u∈V(G)，

1: d(u)＞3.

仿引理2.1的证明，知有过u的C₃、C₄。

2:d(u)=3.

2.1: 若N(u)的导出子图有长为2的路。

则有C₃、C₄

2.2: 若N(u)的导出子图只有一条边且没有过u的C₄。

这时，因没有过u的C₄，所以G-N[u] 每点至多和N(u)中一点相邻。由NC₂≥n-δ，知G-N[u] 是完全子图（因为若G-N[u]有不相邻的两点x,y, 又N(u)中三点至少有一点（认为x₁）和x,y均不相邻。则NC₂≤∣N（x）∪N(y)∣≤n-∣{x,y,u,x₁}|=n-4≤n-δ-1,矛盾）,G∈K₁∨K¹₃:K_n-4（当然K¹₃中任两点在K_n-4中没有公共邻点）。

2.3：若N(u)的导出子图是没有边的3阶空图。

此时，记N(u)={x₁，x₂，x₃},由δ=3，则N(u)中每点在G-N[u]中至少有两个邻点，由NC₂≥n-δ，知N（u）中有两点在G-N[u]中有公共邻点（否则有∣N（x₁）∪N(x₂)∣≤n-∣{N(x₃)\{u}|-|{x₁,x₂}|≤n-4≤n-δ-1,矛盾），则有过u的C₄，又由NC₂+δ≥n，知G-N[u]中每点至少和N(u)中两点相邻。其后，若G=K_n/2.n/2，则引理完成。若G≠K_n/2.n/2，则再分情况讨论：

若∣V(G-N[u])∣=2。

则易知G-N[u]中两点相邻。有过u的C₅。

若∣V(G-N[u])∣＞2。

则G-N[u]中有相邻的两点（因为若G-N(u)中没有相邻的两点，则记x,y为G-N(u)中两点，易知NC₂≤∣N（x）∪N(y)∣≤n-∣V(G-N[u])∣―∣{u}∣≤n-δ-1,矛盾）。有过u的C₅。

引理2.3：2连通n阶图G，NC₂≥n-δ，δ≥4，则G的每点有过它的C₃、C₄或C₄、C₅或G=K_n/2,n/2。

证明：对任意u∈V(G)，

若N(u)的导出子图有长为2的路。

则有过u的C₃、C₄。

若N(u)的导出子图最长路的长是1。

则有过u的C₃，又N(u)中每点在G-N[u]中的邻点数不少于δ-2，由NC₂≥n-δ，知N(u)中有两点在G-N[u]中有公共邻点（因为若没有公共邻点，则记x，y为N(u)中的长是2的两点，

则有∣N(x)∪N(y)∣≤n-2(δ-2)-∣{x,y}∣=n-2δ+2＜n-δ，矛盾），从而有过u的C₄。

若N(u)的导出子图为空图。

此时N(u)中每点在G-N[u]中的邻点数不少于δ-1，由NC₂≥n-δ，类似情况2的分析，知N(u)中有两点在G-N[u]中有公共邻点，即有过u的C₄。也有G-N[u]中每点至少和N(u)中∣N(u)∣-1的点相邻（由NC₂≥n-δ）。其后，若G-N[u]有相邻的两点。则有过u的C₅。若G-N[u]没有相邻两点。由NC₂≥n-δ，知∣V（G-N[u]）∣=δ-1，且∣N(u)∣=δ，即G=K_n/2,n/2。          #

引理2.4：2连通n阶图G，NC₂≥n-δ，C_m是一圈，u是G-C_m的一点，∣Nc_m(u)∣≥2，对任意x∈N^±c_m(u)，x和N(u)\(C_m)中点均不相邻，则V(C_m)∪{u}构成C_m+1。

证明：我们说必有下列结论之一成立：

（1）：存在x_i,x_j∈Nc_m(u),x_i+1x_j+1∈E(G)。

（2）：存在x_i,x_j∈Nc_m(u),P₁=x_i+1x_i+2…x_j-2上x_k,x_k+1满足x_kx_j+1,x_k+1x_i+1∈E(G)或P₂=x_j+1x_j+2…x_i上x_k,x_k+1满足x_kx_i+1,x_k+1x_j+1∈E(G)。(这里V（C_m）\{V(P₁) ∪V(P₂)}={x_j-1,x_j}

这是因为若没有(1)和(2)，记x_i,x_j∈Nc_m(u)且{x_i+1，x_i+2，…，x_j-1}∩Nc_m(u)=Ф(此时的x_i,x_j称为具有性质Ж)

由引理2.4条件知，对任意x∈N[u]。

若d(x_i+1,x_j+1)=2。

当x≠V(C_m)时，x和x_i+1，x_j+1均不相邻。当x=x_k∈V（C_m）时，x_k+1和x_i+1,x_j+1均不相邻，从而NC₂≤∣N（x_i+1）∪N(x_j+1)∣≤n-∣N[u]∣＜n-δ，矛盾。

有(1)，则C_m+1为：x₁x₂…x_iux_jx_j-1…x_i+1x_j+1x_j+2…x_mx₁。

若d(x_i+1,x_j+1)＞2。

当P₁有点和x_j+1相邻时，记x_S为P₁上最先和x_j+1相邻的点，则NC₂=∣N（u）∪N(x_i+1)∣≤n-∣NG_-c_m(x_j+1)∣-(∣N⁺P₁(x_j+1)∣+∣N^-P₂(x_j+1)∣-∣{x_j-1,x_j}∣)- ∣{x_i+1,u,x_S}∣≤n-δ-1, 矛盾。当P₁没有点和x_j+1相邻时，则NC₂=∣N（u）∪N(x_i+1)∣≤n-∣NG_-c_m(x_j+1)∣-(∣N⁺P₁(x_j+1)∣+∣N^-P₂(x_j+1)∣-∣{x_j}∣)- ∣{x_i+1,u}∣≤n-δ-1, 矛盾。

(这里N⁺P₁(x_j+1)={x_h+1∈V（C_m）∣x_h∈NP₁(x_j+1)},N^-P₂(x_j+1)={x_h-1∈V（C_m）∣x_h∈NP₂(x_j+1)}

有(2) 则，若P₁=x_i+1x_i+2…x_j-2上x_k,x_k+1满足x_kx_j+1,x_k+1x_i+1∈E(G)， 则C_m+1为:x₁x₂…x_iux_jx_j-1…x_h+1x_i+1x_i+2…x_hx_j+1x_j+2…x₁。若P₂=x_j+1x_j+2…x_i上x_k,x_k+1满足x_kx_i+1,x_k+1x_j+1∈E(G) ， 则C_m+1为:x₁x₂…x_iux_jx_j-1…x_i+1x_hx_h-1…x_j+1x_h+1x_h+2…x₁。

对于没有(1),还进一步有结论Ⅰ：记x_S为P₂上最后和x_j+1相邻的点，因d(x_i+1,x_j+1)＞2,所以x_S和x_i+1不相邻，若x_S和u也不相邻，则NC₂≤n-δ-2。若x_S和u相邻(此时,因无（1），及u已和x_i相邻，所以u和x_I-1不相邻，即x_S≠x_i-1),有x_S+1x_i+1，x_S+1u∈E（G），则NC₂≤n-δ-2。这说明若没有(1)，则(2)的P₁上有x_k，x_k+1，x_s，x_s+1满足x_kx_j+1,x_k+1x_i+1，x_Sx_j+1，x_S+1x_i+1∈E（G），或P₂上有x_k，x_k+1，x_s，x_s+1满足x_kx_i+1,x_k+1x_j+1，x_Sx_i+1，x_S+1x_j+1∈E（G），或P₁上有x_k，x_k+1和 P₂上有x_s，x_s+1满足x_kx_j+1,x_k+1x_i+1，x_Sx_i+1，x_S+1x_j+1∈E（G）且∣k-s∣≥2。（此时是i＜j的构造）。

引理2.5：2连通n阶图G，NC₂≥n-δ，C_m,C_m+1为过点u的两个圈，则有过u的C_m+2或G=K_n/2,n/2。

证明：假设G≠K_n/2,n/2。

A：若G-C_m中有一点x，满足N^±c_m(x)中有一点和N(x)\V（C_m）中某点相邻。

则有过u的C_m+2。

B：若G-C_m中任一点x，N^±c_m(x)中没有点和N(x)\V（C_m）中点相邻。

再分情况讨论，

G-C_m中存在不同两x，y，满足∣Nc_m(x)∣≥2，∣Nc_m(y)∣≥2。

Nc_m(x)=Nc_m(y)={x_i,x_j}。

此时有xy∈E（G）。这是因为，若xy∈E（G），则记x_k∈V（C_m）\{x_i,x_j}且满足x_k∈{x_i+1,x_j+1},则NC₂≤∣N(x)∪N(y)∣≤n-∣N[x_k]\{x_i,x_j}∣-∣{x,y}∣＜n-δ ，矛盾。

所以xy∈E(G)，由引理2.4的讨论知有引理2.4的(1)或(2)，从而有过u的C_m+2

Nc_m(x)≠Nc_m(y)或max{∣Nc_m(x)∣，∣Nc_m(y)∣}≥3

当xy∈E(G)时。

    因已假设无C_m+2过u，所以先有结论Ⅱ:x和N^±c_m(y)中点均不相邻,及y和N^±c_m(x)中点也均不相邻。

若Nc_m(x)∩Nc_m(y)≠Φ.

    记x_i∈Nc_m(x)∩Nc_m(y)，选取x_j∈Nc_m(x)且x_i,x_j具有性质Ж，则由引理2.4的(1)和(2)知，由x和C_m构成含边xx_i的C_m+1过点u，又因y和x, x_i均相邻，所以有C_m+2过点u。

若Nc_m(x)∩Nc_m(y)=Φ.

若存在C_m上连接的两点x_i ,x_i+1∈Nc_m(x)或Nc_m(x).

   不妨认为x_i ,x_i+1∈Nc_m(x)，则先由x和C_m构成C_m+1过点u，显然Nc_m+1(y)= Nc_m(y)∪{x}，所以存在x_k,x_t∈Nc_m+1(y)且具有性质Ж，则由引理2.4,有C_m+2和过点u.

无1.2.1.1

    先由x和C_m构成C_m+1，则有引理2.4的如下面两图构成情况:

 

 

 

 

  

   

    由结论Ⅱ和情况1.2.1.2知,y和x_i-1,x_i,x_i+1,x_j-1,x_j,x_j+1均不相邻，由情况1.2.1.1知y不能同时和x_i+h ,x_i+k+1均相邻，由C_m+1的构成易知C_m+1上不是x_i-1,x_i,x_i+1,x_j-1,x_j,x_j+1x_i-1,x_i+k,x_i+k+1的点x_h和y相邻时，则x_h-1,x_h+1∈N^±c_m+1(y),从而易有(I) 式：|N⁺c_m+1\{x}(y)∩N^±c_m(y)|=|Nc_m(y)|或|N^-c_m+1\{x}(y)∩N^±c_m(y)|=|Nc_m(y)|。

    这保证存在两点x_h ,x_s∈N⁺c_m+1\{x}(y)或N^-c_m+1\{x}(y)且具有性质Ж.

    其后，因Nc_m+1(y)= Nc_m(y)∪{x}.

    若为引理2.4的(1)时（即d(x_h,x_s)=2时）,易构造出C_m+2

    若无引理2.4的(1)时（即d(x_h,x_s)≥3时）,注意引理2.4的(2)中若无(1)时，导出的矛盾不等式是NC₂≤n-δ-2，而由Nc_m+1(y)= Nc_m(y)∪{x},知若此时无C_m+2过u，则易知至少导出不等式也是NC₂≤n-δ-1,和引理条件矛盾.

从而有C_m+2过的u.

若xy∈E(G).

若x或y和C_m上连接的某两点均相邻.

    不妨认为是x有此情况，则先由x和C_m构成C_m+2. 其后若y和新构成的C_m+1上连接的某两点均相邻，则有C_m+2过u，若y和C_m+1任意连结的两点均不全相邻，则易计算出(II)式：|N⁺c_m+1(y)∩N^±c_m(y)| ≥|Nc_m(y)|-1或|N^-c_m+1(y)∩N^±c_m(y)| ≥|Nc_m(y)|-1。

    因情况2的x和y不相邻，而(II)式左边只比(I)左边至多减少1，所以，类似情况1.2.1.2的分析有C_m+2过的.

无1.2.2.1

    先由x和C_m按引理2.4构成过u的C_m+1，其后若y和新构成的C_m+1上连接的某两点均相邻，,则有C_m+2。若y和C_m+1的任意连接的两点均不全相邻，则同样易有上面(II)式:|N⁺c_m+1(y)∩N^±c_m(y)| ≥|Nc_m(y)|-1或|N^-c_m+1(y)∩N^±c_m(y)| ≥|Nc_m(y)|-1。，所以类似有C_m+2过的u.

G- C_m中至多有一点x。满足∣Nc_m(x)∣≥2.

此时：我们说有过u的C_m+2。

因为若没有过u的C_m+2，则断言〈V(C_m)有m-1阶完全子图。这是因G是2连通的，所以，G-C_m中有一点y,满足∣Nc_m(y)∣=1，记Nc_m(y)={x_i}，则x_i+1和x_i-1相邻，因为若x_i+1和x_i-1不相邻。又没有过u的C_m+2，所以对任意y_i∈N[y]\{x_i},都有y_i和x_i+1,x_i-1均不相邻，从而有NC₂≤∣N(x_i+1)∪N(x_i-1)∣≤n-∣N[y]\{x_i}∣-∣{x_i+1,x_i-1}∣＜n-δ，矛盾。

其后，有d(x_i+2,x_i-1)≤2, 则类似上面的证明，有x_i+1和x_i-1相邻。再其后类似依次证明x_i+3,x_i+4,…,x_i-3,x_i-2和x_i-1均相邻。其后对C_m\{x_i}任意两点x_h,x_k,此时均有d(x_h,x_k)≤2, 类似就可证明x_h和x_k相邻（否则NC₂≤∣N(x_h)∪N(x_k)∣≤n-∣N[y]\{x_i}∣-∣{x_h,x_k}∣＜n-δ，矛盾)。

至此说明<V(C_m)\{x_i}>是m-1阶完全子图。

然后，让路P:y₁y₂…y_k是G-C_m中满足y₁,y_k和C_m上两点(x_i,x_j)分别相邻且k最小的。

当k=2时.

     因<V(C_m)>有m-1阶完全子图，所以，可构造出过u的C_m+2.，矛盾。

当k=3时.

若u和y₁,y_k至少之一相邻.

    考虑到C_m导出图有m-1阶完全子图，从而可构造由含u的C_m上m-1的点构成的路x₁x₂…x_m-1且x₁,x_m-1和y₁,y_k(k=3)分别相邻，也都有含u的路x₁x₂…x_m-1和路y₁y₂y₃构成C_m+2。矛盾

若u和y₁,y_k均不相邻.

若m≥4.

     则同样可构造C_m上的含u的路x₁x₂…x_m-1且x₁,x_m-1和y₁,y_k分别相邻，矛盾

若m=3.

     则由上面已知k=3，所以对任意u₁∈N[u]\V(C₃-u)，u₁和y₁,y₃均不相邻，从而有

|N(y₁)∪N(y₃)|≤n-|N[u]\V(C₃-u)|-|{y₁,y₃}|＜n-δ,矛盾.

当k≥4时.

记C_m上x_i,x_j和y₁,y_k分别相邻，不妨认为|Nc_m(y₁)|=1(情况2)，即Nc_m(y₁)={x_i},此时记x_t∈V(C_m)\{x_i,x_j},对任意x∈N[x_t]\{x_i,y₄},当x∈V(C_m)时，因k≥4, 所以x和y₁,y₃均不相邻（因若x和y₁相邻，此时k=2, 矛盾。若x和y₃相邻, 此时xy₃y₄…y_k的阶比k小，也矛盾）。当x∈V(C_m)\{x_i}时，x和y₁,y₃均不相邻（因Nc_m(y₁)={x_i},即x和y₁不能再相邻。若x和y₃相邻, 此时k=3,矛盾），从而|N(y₁)∪N(y₃)|≤n-|N[x_t]\{x_i,y₄}|-|{y₁,y₃}|＜n-δ, 矛盾。

 

参考文献

1、Faudree RJ,Gould RJ,Jacobson MS,Lesnian L. Neighborhood unions and highly hamilton graphs[J].Ars Combinatoria, 1991,31:139-148

2、Bauer D, Fan GH,Veldman HL. Hamiltonian properties of graphs with large neighborhood unions[J]. Discrete Math.,1991,96:33-49

3、Zhao Ke-wen. Neighborhood condition for pancyclic graphs.Proceedings of  the Third China-USA international conference on Graph Theory,Combinatorics,Algorisms and Applications. World Scientific Publishing.Co Pte Ltd 1994,233-240.

4、Bondy JA. Pancyclic graphs I[J]. J.Combin.Theory,B,1971,11:80-84

5、Faudree RJ,Gould RJ,Jacobson MS,Schelp RH.RH.Extremal problems involving neighborhood unions[J].J.Graph Theory.1987,11:555-564.

6、Faudree RJ,Gould RJ,Jacobson MS,Schelp RH. Neighborhood unions and hamiltonian properies in graphs[J]. J.Combinatorics Theory,B.1989,47:1-9.