研究的图G= (V, E) 均是无向、无重边、无环的图, 图G的最小度和独立数分别用δ和α表示, C_m表示G的长为m的圈, 记为C_m:x₁x₂…x_mx₁, 记S, G₁是G的2个子图, N_S (G₁) ={u∈V (S) :v∈V (G₁) , uv∈E (G) }, N_G (u) 简写为N (u) , N⁺_Cm (G₁) ={x_i+1:x_i∈N_Cm (G₁) }, N^-_Cm (G₁) ={x_i-1:x_i∈N_Cm (G₁) }。其他定义见文献^[1]。

1984年Fan^[2]得到结果:

定理1^[2] 若2连通n阶图G的距离为2的任意2点x, y均有max{d (x) , d (y) }≥n/2, 则G是哈密尔顿图。

1993年Chen^[3]再深化Fan条件, 得到:

定理2^[3] 若2连通n阶图G的满足1≤|N (x) ∩N (y) |≤α-1的不相邻的任2点x, y均有max{d (x) , d (y) }≥n/2, 则G是哈密尔顿图。

1991年Faudree, Gould, Jacobson 和Lesniak^[4]得到邻域并的结果:

定理3^[4] 若2连通n阶图G不相邻的任意2点x, y均有|N (x) ∪N (y) |≥n-δ, 则G是哈密尔顿图。

1991年尹家洪^[5]再考虑距离为2的2点的邻集并 (也称为邻域并) , 并且得到:

定理4^[5] 若2连通n阶图G的距离为2的任意2点x, y均有|N (x) ∪N (y) |≥n-δ, 则G是哈密尔顿图。

笔者进一步深化上面结果, 并且得到结果:

定理5 若2连通n阶图G的满足1≤|N (x) ∩N (y) |≤α-1的不相邻的任2点x, y均有|N (x) ∪N (y) |≥n-δ-1, 则G是哈密尔顿图, 或G∈{K _{(n-1) /2, (n+1) /2}, K^*₂∨3K _{(n-2) /3}} (这里K^*₂仅是2阶图) 。

引理1 对2连通n阶图G, 记C_m是图G的最长圈, G₁为G-C_m的一分支, x_i+1, x_j+1∈N_Cm (G₁) 且{x_i+1, x_i+2, …, x_j-1}∩N_Cm (G₁) =, 记x∈V (G₁) , x_i+1∈ (x) N⁺_Cm (x) , 则有1≤|N (x_i+1) ∩N (x) |≤α-1及|N (x_i+1) ∩N (x_j+1) |≤α-1。

证明 假设有|N (x_i+1) ∩N (x) |≥α。此时, 因C_m是图G的最长圈, 知x和x_i+1在G-C_m中没有公共邻点 (否则, 若x和x_i+1在G-C_m中有公共邻点v, 则有圈C^*:x_ix v x_i+1x_i+2 … x_i比C_m长, 矛盾) , 所以x和x_i+1的公共邻点全在C_m中, 即|N⁺_Cm (x) |≥α, 因C_m是最长圈, 则易知N⁺_Cm (x) ∪{x}是独立点集且点数多于α (否则, 若x_i+1, x_j+1∈N⁺_Cm (G₁) , 使x_i+1x_j+1∈E (G) , 则圈C^*:x_ixx_jx_j-1… x_i+1x_j+1x_j+2…x_i比C_m长, 矛盾) , 即独立数≥α+1, 与独立数是α矛盾。所以, 有|N (x_i+1) ∩N (x) |≤α-1。

假设|N (x_i+1) ∩N (x_j+1) |≥α。此时, 因C_m是最长圈, 显然N (x_i+1) ∩N (x_j+1) 没有点在G-C_m中 (否则, 若G-C_m中的点u∈N (x_i+1) ∩N (x_j+1) , 则记P为G₁中1条两端点分别与x_i和x_j相邻的路, 当u∉V (P) , 则有圈C^*:x_iPx_jx_j-1…x_i+1ux_j+1x_j+2…x_i比C_m长, 矛盾;当u∈V (P) , 因P有点与x_i相邻, 并且u与x_i+1相邻, 从而G₁中存在1条两端点分别与x_i和x_i+1相邻的路P^*, 则也有圈C:x_iP^*x_i+1x_i+2…x_i比C_m长, 矛盾) , 所以N (x_i+1) ∩N (x_j+1) 中点全在C_m中, 即|N (x_i+1) ∩N (x_j+1) |=|N_Cm (x_i+1) ∩N_Cm (x_j+1) |=|N^-_Cm (x_i+1) ∩N^-_Cm (x_j+1) |, 又C_m是最长圈, 所以N^-_Cm (x_i+1) ∩N^-_Cm (x_j+1) 全部点与G₁中任取1点组成的点集中没有相邻的两点 (如, 若x_k-1, x_h-1∈N^-_Cm (x_i+1) ∩N^-_Cm (x_j+1) , 使x_k-1x_h-1∈E (G) :a.当x_k-1∈{x_i+2, x_i+3, …, x_j}, x_h-1∈{x_j+2, x_j+3, …, x_i}时, 记P为G₁中1条两端点分别与x_i和x_j相邻的路, 则有圈C^*:x_iPx_jx_j-1…x_kx_j+1x_j+2…x_h-1x_k-1x_k-2…x_i+1x_hx_h+1…x_i比C_m长, 矛盾; b.当x_k-1, x_h-1∈{x_j+2, x_j+3, …, x_i}时, 不妨认为h≥k+1, 则有圈C^*:x_iPx_jx_j-1…x_i+1x_kx_k+1…x_h-1x_k-1x_k-2…x_j+1x_hx_h+1…x_i比C_m长, 矛盾) , 即这样的点一共不少于α+1, 与独立数是α矛盾。所以|N (x_i+1) ∩N (x_j+1) |≤α-1。

引理2 若2连通n阶图G满足1≤|N (x) ∩N (y) |≤α-1的不相邻的任2点x, y均有|N (x) ∪N (y) |≥n-δ-1, C_m是最长圈, G₁为G-C_m的一分支, x_i+1, x_j+1∈N⁺_Cm (G₁) , 且{x_i+1, x_i+2, …, x_j-1}∩N_Cm (G₁) =, 则d (x_i+1, x_j+1) =2。

证明 假设d (x_i+1, x_j+1) ≠2。因C_m是最长圈, 易有x_i+1, x_j+1∉E (G) , 则d (x_i+1, x_j+1) ≥3, 记x∈V (G₁) 且x与C_m的x_i相邻, a.记x_k∈{x_i+2, x_i+3, …, x_j}与x_j+1相邻, 且满足{x_i+1, x_j+2, …, x_k-1}∩N_Cm (x_j+1) =的点, 因d (x_i+1, x_j+1) ≥3, 所以x_k与x_i+1, x均不相邻。b.记x_h∈{x_j+2, x_i+3, …, x_i}与x_j+1相邻, 且满足{x_h+1, x_h+2, …, x_i}∩N_Cm (x_j+1) =的点, 因d (x_i+1, x_j+1) ≥3, 所以x_h与x_i+1不相邻, 若x_h与x也不相邻, 则x_h与x_i+1, x均不相邻。若x_h与x相邻, 因C_m是最长圈, 则易知x_h+1与x_i+1, x均不相邻。c.因C_m为最长圈, 所以若{x_i+2, x_i+3, …, x_j}x_j-1, x_j}中的点x_h与x_j+1相邻时, 则x_h+1与x_i+1, x均不相邻 (否则, 如果x_h+1与x_i+1相邻, 则记P为G₁中1条两端点分别与x_i和x_j相邻的路, 有圈C^*:x_iPx_jx_j-1…x_h+1x_i+1x_i+2…x_hx_j+1x_j+2…x_i比C_m长, 矛盾;因{x_i+1, x_i+2, …x_j-1}∩N_Cm (G₁) =, 所以x_h+1与x不相邻) 。若{x_j+1, x_j+2, …, x_i}中的点x_h与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长, 矛盾;若x_h-1与x相邻, 则记P^*为G₁中1条两端点分别与x_h-1和x_j相邻的路, 则有圈C^*:x_jPx_h-1x_h-2…x_j+1x_hx_h+1…x_j比C_m长, 矛盾) ;又G-C_m中点v与x_j+1相邻时, v与x_i+1, x均不相邻, 从而|N (x_i+1) ∪N (x) |≤n-|N (x_j+1) x_j-1, x_j}|-|{x_k, x_i+1, x, x_h+1}|≤n-δ-2, 结合引理知, 应有|N (x_i+1) ∪N (x) |≥n-δ-1, 矛盾。若{x_i+2, x_i+3, …, x_j}x_j}中没有点与x_j+1相邻时, 则|N (x_i+1) ∪N (x) |≤n-∣N (x_j+1) x_j}|-|{x_i+1, x, x_h+1}|≤n-δ-2, 结合引理知, 应有|N (x_i+1) ∪N (x) |≥n-δ-1, 矛盾。

引理3 若2连通n阶图G的满足1≤|N (x) ∩N (y) |≤α-1的不相邻的任2点x, y均有|N (x) ∪N (y) |≥n-δ-1, C_m是最长圈, G₁为G-C_m的一分支, 则G₁中与C_m中某点相邻的点u必与G₁中每一点都相邻。

证明 假设G₁中点u与x_i相邻, 而G₁中有点v与u不相邻。此时, 因C_m是最长圈, 记x_i+1, x_j+1∈N⁺_Cm (G₁) , 且{x_i+1, x_i+2, …, x_j-1}∩N_Cm (G₁) =, 由引理1和引理2知, 1≤|N (x_i+1) ∩N (x_j+1) |≤α-1, 则|N (x_i+1) ∪N (x_j+1) ∣≤n-|N_G-Cm (u) |-|N⁺_Cm (u) |-|{u, v}|≤n-δ-2, 与应有|N (x_i+1) ∪N (x_j+1) |≥n-δ-1, 矛盾。

证明 假设图G不是哈密尔顿图, 记C_m为G的一个最长圈, 分情况讨论如下:

1) 情况1 存在G-C_m的一分支G₁, |N_Cm (G₁) |≥3, 此时, 断言|V (G-C_m) |=1。

先证明|V (G₁) |=1。假设|V (G₁) |≥2, 记x_i+1, x_j+1, x_h+1∈N⁺_Cm (G₁) , 且{x_i+1, x_i+2, …, x_j-1, x_j+1, x_j+2, …, x_h-1}∩N (G₁) =, 由引理2知, 则d (x_i+1, x_j+1) =d (x_j+1, x_h+1) =2。由引理3知, 若G₁中2点u, v与C_m中2点相邻, 则uv∈E (G) , 因C_m是最长圈, 所以显然x_h+2∉N⁺_Cm (G₁) , 又|V (G₁) |≥2, 在引理3之下, x_h+1与x_i+1, x_j+1均不相邻, 从而|N (x_i+1) ∪N (x_j+1) |≤n-|V (G₁) |-|N⁺_Cm (G₁) |-|{x_h+2}|<n-δ-1, 矛盾。

再证G-C_m的分支数是1。因为若G-C_m的分支数≥2, 则记G-C_m的另一分支为G₂, 和v∈V (G₂) , 因C_m为最长圈, 则v不能与N⁺_Cm (G₁) 中2点相邻, 这样就有v与x_i+1, x_j+1或x_i+1, x_h+1均不相邻 (认为v与x_i+1, x_j+1均不相邻) , 则|N (x_i+1) ∪N (x_j+1) ∣≤n-|V (G₁) |-|N⁺_Cm (G₁) |-|{v}|≤n-δ-2, 矛盾。

说明断言正确, 记G-C_m={u}。

a.子情况1.1 若C_m上有连接的2点x_h, x_h+1∉N_Cm (u) 及间隔的x_i, x_i+2∈N_Cm (u) 。

此时可找到这样的3点x_j, x_j+1∉N_Cm (u) , 而x_j+2∈N_Cm (u) , 因C_m为最长圈, 所以x_j+1与x_i+1, u均不相邻, 从而|N (x_i+1) ∪N (u) |≤n-|N⁺_Cm (u) |-|{u}|-|{x_j+1}|≤n-δ-2, 矛盾。

b.子情况1.2 对N_Cm (u) 中任2点x_ix_i+r均有r≥3。

此时, 记x_i+1, x_j+1, x_h+1∈N⁺_Cm (G₁) , 且{x_i+1, x_i+2, …, x_j-1, x_j+1, x_j+2, …, x_h-1}∩N_Cm (G₁) =, 则d (x_i+1, x_j+1) =d (x_j+1, x_h+1) =2。则|N (x_i+1) ∪N (x_j+1) ∣≤n-|N⁺_Cm (u) |-|{u}|≤n-δ, 知N^-_Cm (u) 中每一点均和与x_i+1, x_j+1之一相邻, 即记x_i-1与x_i+1, x_j+1之一相邻;同样由|N (x_j-1) ∪N (x_h-1) |≤n-|N^-_Cm (u) |-|{u}|≤n-δ, 知x_i-2与x_j-1, x_h-1之一相邻, 从而易有比C_m长的圈, 矛盾。

c.子情况1.3 除子情况1.1和子情况1.2外的情况。

此时, 必有这样的情况:x₁, x₃, …, x_n-2 (或x₂, x₄, …, x_n-1) 每点与u均相邻, 又因C_n-1是最长圈, 所以C_n-1上没有连接的2点与u均相邻, 以及N⁺_Cm (u) 中没有相邻的2点。从而G=K _{(n-1) /2, (n+1) /2}。

2) 情况2 对G-C_m的任一分支G₁, 均有|N_Cm (G₁) |=2, 则断言G-C_m的分支数=1。

这是因为若G-C_m的分支数≥2, 记G_i (i=1、2) 是G-C_m的2个分支, 记N_Cm (G₁) ={x₁, x_i}, 因C_m是最长圈, 所以G₂中的点至多与x₂, x_i+1之一相邻 (否则, 若G₂中有2点与x₂, x_i+1分别相邻, 则记P¹为G₁中1条两端点分别与x₁和x_i相邻的路, P²为G₂中1条两端点分别与x₂和x_i+1相邻的路, 则有圈C^*:x₁P¹x_ix_i-1…x₂P²x_i+1x_i+2…x_j比C_m长, 矛盾) , 可认为G₂中的点与x₂均不相邻, 记u∈V (G₁) , x₂∈N⁺_Cm (u) , 从而|N (x₂) ∪N (u) |≤n-|V (G₂) |-|{u, x₂, x_i+1}|, 又因|N_Cm (G₂) |=2, 显然有|V (G₂) |≥δ-1, 所以|N (x₂) ∪N (u) |≤n-δ-2, 矛盾。

其后记G-C_m=G₁, 由n-δ-1≤|N (x₂) ∪N (x_i+1) ∣≤n-|V (G₁) |-|{x₂, x_i+1}|, 知|V (G₁) |=δ-1。因|N_Cm (G₁) |=2, 即G₁中每点和C_m上至多2点相邻, 知G₁中每点都与G₁中其余点全相邻 (否则, 将有1点的度数≤δ-1, 矛盾) , 从而G[V (G₁) ]是完全子图。

记V₁={x₂, x₃, …, x_i-1}, V₂={x_i+1, x_i+2, …, x_m}, V₃=V (G₁) 。

显然, 因G[V (G₁) ]是完全子图, 且|V (G₁) |=δ-1, 若|{x_i+1, x_i+2, …, x_m}|>δ-1, 则因C_m是最长圈, 显然x₂与{x_i+1, x_i+2, …, x_i+δ-1}中的点均不相邻, x_i-1与{x_{m- (δ-2)} , x_{m- (δ-3)} , …, x_m}中的点均不相邻, 记u∈V (G₁) 与x₁相邻, 以及由|N (x₂) ∪N (u) ∣≤n-|{x_i+1, x_i+2, …, x_δ-1}|-|{x₂, u}|≤n-δ, 知{x_i+δ, x_i+δ+1, …, x_m}中的点与x₂均相邻;类似有{x_i+1, x_i+2, …, x_{m- (δ-1)} }中的点与x_i-1均相邻;此时, 将有{x_i+1, x_i+2, …, x_m}中的2点x_h, x_h+r与x₂, x_i-1分别相邻, 且r≤|V (G₁) |, 则易有比C_m长的圈x₁G₁x_ix_i+1…x_hx₂x₃…x_i-1x_h+rx_h+r+1…x₁, 或x₁G₁x_ix_i+1…x_hx_i-1x_i-2…x₂x_h+rx_h+r+1…x₁, 矛盾。

从而, 只能有|{x₂, x₃, …, x_i-1}|=δ-1和|{x_i+1, x_i+2, …, x_m}|=δ-1。类似上面知G[V₁]是完全子图, 且G[V₂]也是完全子图。显然, 因|V_k|=δ-1, (k=1, 2, 3) , 知V_k每一点与x₁, x_i均相邻, 这样就有G∈K^*₂∨3K _{(n-2) /3} (这里K^*₂为二阶图) 。

至此, 完成定理的证明。

在诸学者研究^[2,3,4,5]的基础上, 笔者进一步深化得到:若2连通n阶图G的满足1≤|N (x) ∩N (y) |≤α-1的不相邻的任2点x, y均有|N (x) ∪N (y) |≥n-δ-1, 则G是哈密尔顿图, 或G∈{K _{(n-1) /2, (n+1) /2}, K^*₂∨3K _{(n-2) /3}}, K^*₂仅是2阶图。

图论已在信息工程技术方面的应用做了一些尝试^[1,6], 在信息智能化管理系统方面图论的应用已产生一定的影响。互联网络有三大要素:节点间互联拓扑 (包括连接通路) 、开关元件和控制方式, 而连接通路就是图的哈密尔顿圈结构等。这方面Efe给出一类图的工作^[7], 最近樊建席等研究BC图的哈密尔顿圈和路结构等并提出一个猜想^[8]。这些研究是比上面2类特殊图更为一般又符合一些著名条件的图的一类圈结构。下一步将进一步研究图论, 并在信息科学上开展应用研究工作。

笔者谨以此文祝贺琼州大学数学与信息科学研究所成立!