基于無向圖的哈密爾頓性存在的若干結(jié)果

陳帥君，徐美進，李永明

（遼寧工業(yè)大學(xué) 理學(xué)院，遼寧 錦州 121001）

0 引言

圖論以1736年歐拉提出的“哥尼斯堡七橋問題”為起源，經(jīng)歷了近300年的發(fā)展沉淀，至今無論是在理論或是應(yīng)用方面它都有著極其重要的價值. 所謂圖論就是對某些點和連接這些點的線所組成集合的某些性質(zhì)的研究，對于某個連通圖來說，經(jīng)過該圖的每條邊的跡，稱之為歐拉跡；若存在某條路覆蓋了每條邊恰好一次的回路，稱之為歐拉環(huán)游，含有歐拉環(huán)游的圖稱之為歐拉圖. 若存在某條路覆蓋了每個頂點恰好一次，則稱之為哈密爾頓路；假如這樣的路是一條回路，則稱這樣的路為哈密爾頓回路；含有哈密爾頓回路的圖，稱之為哈密爾頓圖. 若圖中的任意兩個頂點都有哈密爾頓路連接著，那么稱這類圖為哈密爾頓連通圖.

圖的哈密爾頓性是結(jié)構(gòu)圖論一個非常重要而且意義深遠的研究課題，該問題的產(chǎn)生和發(fā)展與著名的四色猜想研究密切相關(guān)，因而備受國內(nèi)外眾多圖論專家和學(xué)者的關(guān)注. 圖的哈密爾頓路問題與結(jié)構(gòu)圖論中哈密爾頓性的研究也是密切相關(guān)的. 從算法復(fù)雜性來講，判定一個圖是否存在一條哈密爾頓路是NP-完全的. 對于某個圖是歐拉圖成立的條件已經(jīng)解決：一個非空連通圖含有歐拉跡當且僅當其最多含有兩個奇點；一個非空的連通圖是歐拉圖當且僅當它沒有奇點. 如圖1哥尼斯堡七橋圖，圖2為其簡化圖. 圖2四個頂點都是奇點，因此從任意點出發(fā)無法完成每座橋走一次從而走遍全部七座橋的任務(wù)，因此圖2不是歐拉圖且其不含歐拉跡. 但對于哈密爾頓圖的判定，還是一個未解之謎，數(shù)學(xué)家們正在逐漸得使圖的哈密爾頓性成立的充分條件更加嚴格化. 本文第一部分主要簡述了圖論的發(fā)展概述及圖的某些基本概念和性質(zhì). 第二部分主要概括了某圖在參數(shù)條件下哈密爾頓圖成立的某些條件. 第三部分主要闡述了圖在某些禁用子圖的條件下哈密爾頓性質(zhì)成立的某些重要性質(zhì)，最后針對半無爪圖的哈密爾頓性提出了一個有關(guān)猜想.

圖1 哥尼斯堡七橋圖

圖2 七橋簡化圖

1 符號定義

本文中我們考慮的都是階數(shù)為n的有限、無向簡單圖G= (V(G)，E(G))，即無環(huán)也無重邊，文中其他未定義到的術(shù)語和符號見參考文獻［1］. 設(shè)G是一個圖，其中V(G)和E(G)分別代表圖G的頂點集和邊集，圖G的階數(shù)指V(G)的大小，通常用n表示，Pn表示含有n個頂點的路，d(x)表示頂點x的度數(shù)，即與頂點相連的邊的條數(shù)，d(x，y)表示任意兩頂點x，y之間的最短路的長度，稱其為兩點之間的距離，最小度δ(G)表示圖G中度數(shù)最小的點的度數(shù)，即δ(G)= min{d(v) ，v∈G} ，對于V(G)的任意非空子集S，以S為頂點集，以兩端點均在S中的邊的全體為邊集組成的子圖稱為G的導(dǎo)出子圖. 圖G中不含有同構(gòu)于H的導(dǎo)出子圖，則稱圖G禁用子圖H，也稱H為圖G的禁用子圖. 爪（K1，3）是其中一個頂點度是3其余點的度為1的四個頂點組成的連通圖，某圖的任意導(dǎo)出子圖不同構(gòu)于爪稱其為無爪圖（K1，3-free）. 對于?x，y∈V(G)，其中令J(x，y)={u∈N(x)?N(y)∶N[u]?N[x]?N[y]}，當d(x，y)= 2時，J(x，y)≠φ，則稱圖G是半無爪圖. 若圖G的頂點的度均為k，則G稱為k-正則圖. 給定一個整數(shù)k，圖G的k-正則生成子圖稱為G的k-因子. 若V(G)的子集V'(G)使得G-V'(G)不連通，則稱V'(G)為圖G的頂點割，若G中至少有一對相異的不相鄰頂點，則G的頂點割元素最少的叫做G的連通度，記為κ(G). 若κ(G)≥k，則稱G是k-連通的.

2 通過某些參數(shù)角度定義哈密爾頓圖

對圖的哈密爾頓性質(zhì)研究最先從圖的某些參數(shù)出發(fā)，這樣的性質(zhì)較為直接，以下兩個定理分別在1952年由Dirac［2］和1960年Ore［3］最先提出，在很長一段時間內(nèi)這是具有標志性作用的兩個定理，之后繼續(xù)引入了圖的閉包［4］和獨立數(shù)［5］等來描述圖的哈密爾頓性質(zhì).

定理2.1［2］設(shè)圖G是n階簡單圖并且n≥3，圖中最小度δ≥n2，則G是哈密爾頓圖.

定理2.2［3］設(shè)圖G是n階簡單圖并且n≥3，圖中任意兩個不相鄰的頂點對的度數(shù)之和至少為n，則G是哈密爾頓圖.

定理2.3［4］設(shè)階數(shù)為n的圖G包含一個哈密爾頓圈當且僅當反復(fù)連接G中所有滿足度數(shù)之和至少為n的不相鄰頂點對，得到的新圖G'含有哈密爾頓圈.

1972年V. Chvátal利用β0()G定義圖G的獨立數(shù)，即圖G中獨立集元素的最大值，得到如下重要定理：

定理2.4［5］設(shè)圖G的連通度為k，滿足β0(G)≤k，則圖G是哈密爾頓圖.

這些原始定理的提出，開創(chuàng)了一些新的研究方法，提出了圖具有哈密爾頓性的充分條件. 在通過其閉包后的新圖G'的哈密爾頓性來研究原圖的哈密爾頓性，放松了對圖的要求，對以后研究某圖具有哈密爾頓性具有重要作用. 在這些定理的推廣方面，數(shù)學(xué)家們做了大量的工作，這是哈密爾頓圖論的核心課題之一，其他一些結(jié)果可參考文獻［6-12］.

3 通過某些禁用子圖角度定義哈密爾頓圖

圖的哈密爾頓性問題是結(jié)構(gòu)圖論中極其重要且意義深遠的一個課題，禁用子圖與圖的很多性質(zhì)都有著密切的聯(lián)系，比如，禁用子圖與圖的哈密爾頓連通性，禁用子圖與圖的染色、2 -因子，禁用子圖與圖的泛圈性等問題都有密切的聯(lián)系.

自從Beineke在1970年發(fā)表了有關(guān)線圖性質(zhì)的文章后［13］，大家開始研究無爪圖的性質(zhì). 在線圖都是無爪圖這個研究背景下，二十世紀七八十年代，對于無爪圖的路圈性質(zhì)的研究也開始起來了，如果圖G中不含有同構(gòu)于K1，3（完全二部圖）的導(dǎo)出子圖，則稱圖G是無爪圖（K1，3-free），也稱K1，3是該圖的禁用子圖，K1，3-free同理可知.

關(guān)于禁用子圖與圖的哈密爾頓連通性問題的研究，在1979年D. J. Oberly［14］和G. Chartrand［15］率先提出如下定理：

定理3.1［14］任意的階數(shù)n≥3的連通的、局部連通無爪圖G是哈密爾頓圖.

定理3.2［15］一個3 -連通的、局部連通無爪圖是哈密爾頓連通的.

后來，1984年Kanetkar和Rao［16］嚴格化了G. Chartrand的上述定理，將3 -連通改為2 -連通并證明了其結(jié)果的正確性.

1985年M. M. Matthews和D. P. Summer［17］也得到了關(guān)于無爪圖有Hamilton圈的重要結(jié)果：

定理3.3［17］設(shè)圖G是n階2 -連通無爪圖，如果?v∈V(G)，d(v)≥(n- 2)3，則G中含有哈密爾頓圈，即圖G是哈密爾頓圖.

1986年，劉一萍等［18］用三個不相鄰頂點的度和條件得到了無爪圖有Hamilton圈的充分條件：

定理3.4［18］設(shè)圖G是n階2 -連通無爪圖，如果δ3()G≥n- 2，那么圖G中含有哈密爾頓圈，即圖G是哈密爾頓圖.

1989年，E. Flandrin［19］等人給出了下面的結(jié)果：

定理3.5［19］設(shè)圖G是n階2 -連通無爪圖，如果G中任意一對不相鄰的頂點u，v滿足d()u+d()

v≥(2n- 5)3，則G有Hamilton圈.

1996年，A. S. Asratian［20］在定理3.2的基礎(chǔ)之上提出并證明了如下結(jié)論：

定理3.6［20］設(shè)圖G是局部連通的無爪圖，則G是哈密爾頓連通的當且僅當圖G是3 -連通的.

2012年，馬修山，王江魯［21］證明了下面結(jié)果：

定理3.7［21］設(shè)圖G是n階2 -連通無爪圖，如果G中任意兩個同構(gòu)于K2（2階完全圖）的不相鄰子圖點H1和H2的度之和滿足d(H1)+d(H2)≥n- 3，則G有Hamilton圈.

2013年，徐珊珊，王江魯［22］將其擴展至3 -連通無爪圖上研究，提出了如下兩個定理：

定理3.8［22］設(shè)圖G是n階2 -連通無爪圖，如果G中任意兩個分別同構(gòu)于P（33個頂點的路）和K（22階完全圖）的不相鄰子圖點H1和H2的度之和滿足d(H1)+d(H2)≥n- 2，則G有Hamilton圈.

定理3.9［22］設(shè)圖G是n階3 -連通無爪圖，如果G中任意兩個分別同構(gòu)于K（33階完全圖）和K1的不相鄰子圖點H1和H2的度之和滿足d(H1)+d(H2)≥n- 3，則G有Hamilton圈.

2014年，米晶［23］證明了如下結(jié)論：

定理3.10［23］設(shè)圖G是n階2 -連通無爪圖，如果G中任意兩個分別同構(gòu)于P3和K1的不相鄰子圖點H1和H2的度之和滿足d(H1)+d(H2)≥n，則G中含有Hamilton圈.

定理3.11［23］設(shè)圖G是n階2 -連通無爪圖，如果G中任意兩個分別同構(gòu)于K3和K2的不相鄰子圖點H1和H2的度之和滿足d(H1)+d(H2)≥n- 3，則G有Hamilton圈.

同年，孫運偉［24］研究無爪圖的路圈性質(zhì)后得到了以下結(jié)論：

定理3.12［24］設(shè)圖G是n階2 -連通無爪圖，如果G中任意兩個分別同構(gòu)于K1和K2的不相鄰子圖點H1和H2的度之和滿足d(H1)+d(H2)≥n- 3，則G的任意最長圈是Hamilton圈，特別的，這里說明了其下屆“n-3” 是最好的.

2016年，鄭偉，王力工［25］得到如下相關(guān)定理：

定理3.13［25］設(shè)圖G是n階3 -連通且最小度δ(G)≥4的無爪圖，如果G中任意兩個分別同構(gòu)于P（44個頂點的路）和K1的不相鄰子圖點H1和H2的度之和滿足d(H1)+d(H2)≥n，則G是哈密爾頓連通的.

2016年，尹君［26］利用導(dǎo)出圈的性質(zhì)來判斷圖的哈密爾頓性，證明了以下定理：

定理3.14［26］對于3 -連通的線圖，若它不含長度超過8的導(dǎo)出圈，則該圖是哈密爾頓圖，同時證明了對于3 -連通的無爪圖，若它的每個長度至少為4的導(dǎo)出圈中至多含有8條非奇異邊，則該無爪圖是哈密爾頓圖；若它每個長度至少為4的導(dǎo)出圈中至多含有11條非奇異邊，則要么它是哈密爾頓圖，要么它的閉包是經(jīng)過收縮可變?yōu)镻etersen圖（圖3）的線圖.

圖3 Petersen圖

定理3.15［26］任意2 -連通的無爪圖，若它最長的導(dǎo)出圈的長度不小于n- 2，那么該圖是哈密爾頓圖.

定理3.16［26］最小度δ≥3的n階無爪圖，若它含有長度超過(4n- 2δ- 4)δ+2的導(dǎo)出圈，則它是哈密爾頓圖. 然后證明了當δ∈{ 3，4} 時，上述結(jié)果是最好的.

2018年，Benjamin Momège［27］在K1，4-free圖哈密爾頓性研究方向上得到新的進展，如下：

定理3.17［27］若連通圖G的最小度δ(G)≥2n3并且圖G是K1，4-free的，則G中包含了一條哈密爾頓路.

2020年，石開欣，任韓［28］得到以下結(jié)論：

定理3.18［28］設(shè)圖G是n階3 -連通無爪圖，如果G中任意兩個分別同構(gòu)于K1和P4的不相鄰子圖點H1和H2的度之和滿足d(H1)+d(H2)≥n- 2，則G有Hamilton圈.

定理3.19［28］設(shè)圖G是n階3 -連通無爪圖，其中n≥12，如果G中任意兩個分別同構(gòu)于K2和P4的不相鄰子圖點H1和H2的度之和滿足d(H1)+d(H2)≥n- 3，則G有Hamilton圈.

定理3.20［28］設(shè)圖G是n階3 -連通無爪圖，滿足δ(G)≥4，如果G中任意兩個分別同構(gòu)于K2和P4的不相鄰子圖點H1和H2的度之和滿足d(H1)+d(H2)≥n- 1，則G是哈密爾頓連通的.

近年來，由無爪圖引申出另一新的概念：半無爪圖［29］. 對圖G中任意距離為2的點x和y，存在u∈N(x)?N(y)，滿足N(u)?N(x)?N(y)，則G稱為半無爪圖. 一個圖是無爪圖(CF)，則該圖一定也是半無爪圖(QCF)，反之則不成立，即CF∈QCF，因此半無爪圖是對無爪圖的一定程度上的擴展，許多滿足無爪圖哈密爾頓性的條件在半無爪圖上同樣適用. 關(guān)于半無爪圖的哈密爾頓性有如下重要定理：

定理3.21［29］一個κ-連通的半無爪圖G(κ≥2)，如果α(G2)≤κ，則G是哈密爾頓圖.

在Fan-type條件下P. Bedrossian［31］將Fan［30］的結(jié)果進行了輕微的改善，A. Ainouche［29］又在這一基礎(chǔ)之上行了如下改進：

定理3.22［30］設(shè)圖G是一個階數(shù)n≥3的2 -連通圖，令u和v是G中不相鄰的兩個頂點，滿足d( u，v)=2 ?max(d(u)，d(v))≥n2，則G中有哈密爾頓圈.

定理3.23［31］設(shè)圖G是階數(shù)為n的2 -連通圖，若d(x，y)= 2 ?max{d(x)，d(y)}≥n2對于G的導(dǎo)出爪圖（K1，3）或?qū)С鲂拚D（K1，3+e，e是一條邊）中的每一對頂點都成立，則G是哈密爾頓圖.

定理3.24［29］設(shè)圖G是一個2 -連通的簡單圖，圖G滿足條件d(x，y)= 2，{z∈N(x)?N(y)|d(z)= 2} =φ并且d(x)≤d(y)

定理3.25［29］若圖G是κ-連通的半無爪圖(κ≥2)，如果對于G中的任意基數(shù)為κ+1的獨立集X，都有則G是哈密爾頓圖.

2007年，孫淑霞［32］在上述定理的基礎(chǔ)上證明了：

定理3.26［32］若圖G是κ-連通的半無爪圖(κ≥2)，如果對于G2中的任意基數(shù)為κ+1的獨立集X，都有則G是哈密爾頓圖.

2019年，陳曉東［33］對半無爪圖的Ore哈密爾頓充分性條件進行了改進，提出如下定理：

定理3.27［33］對任意的階數(shù)為n的半無爪圖G，若σk+1(G)≥n-k（k是正整數(shù)），則p(G)≤k，其中σk+1(G)是圖G中k+1個頂點的獨立集中的最小度和，p(G)= min{ | Ρ |：Ρ是一條覆蓋G的路}.

針對李明楚［34］在1993提出的關(guān)于無爪圖的某條哈密爾頓性質(zhì)，2003年李饒［35］證明了原條件同樣適用于半無爪圖，如下：

定理3.28［34］設(shè)圖G是n階3 -連通無爪圖并且最小度δ(G)≥(n+5)5，則圖G是一個哈密爾頓圖.

定理3.29［35］設(shè)圖G是n階3 -連通半無爪圖并且最小度δ(G)≥(n+5)5，則圖G是一個哈密爾頓圖.

同樣的類似推理，李饒［37］證明了如下的無爪的哈密爾頓圖的性質(zhì)在半無爪圖中同樣適用：

定理3.30［36］設(shè)圖G是n階2 -連通無爪圖并且最小度δ(G)≥n4，則圖G是一個哈密爾頓圖或者G∈?，?為連通度為2的非哈密爾頓圖的集合.

定理3.31［37］設(shè)圖G是n階2 -連通半無爪圖并且最小度δ(G)≥n4，則圖G是一個哈密爾頓圖或者G∈?，?為連通度為2的非哈密爾頓圖的集合.

定理3.32［27］設(shè)圖G是一個階數(shù)為n的連通圖，如果G是K1，4-free的并且σ2(G)≥2n3，則圖G包含一條哈密爾頓路.

引理3.1［27］設(shè)圖G是一個階數(shù)為n的圖并且1 ≤k≤k' ≤n，則σk'(G)≥(k'σk'(G))k.

猜想3.1 設(shè)圖G是一個階數(shù)為n的連通圖，如果G是σ3(G)≥n的半無爪圖，則圖G包含一條哈密爾頓路.

4 結(jié)束語

圖的哈密爾頓性的研究在生活中有著極其廣泛的應(yīng)用，例如近年來興起的快遞服務(wù)業(yè)，尋找盡可能短的一條路線走完所有的目的地，就是一類典型的哈密爾頓應(yīng)用問題. 本文針對無向圖的哈密爾頓性成立的各類條件，在某些參數(shù)或禁用子圖的先決條件下，以時間為順序，對無向圖的哈密爾頓性成立的各類條件進行了概括梳理. 而后結(jié)合部分定理，給出一個相關(guān)猜想.