圖的哈密頓[a，b]-因子的若干結(jié)果.pdf

1、二十世紀(jì)六十年代以來，圖論獲得了空前發(fā)展，在物理學(xué)、化學(xué)、計算機(jī)科學(xué)等學(xué)科中得到了廣泛應(yīng)用。圖的因子理論是圖論的一個重要分支，也是圖論研究中最活躍的課題之一。 本文考慮的圖若無特殊聲明均為簡單、無向有限圖，對于一個圖G=G（V（G），E（G）），我們用V（G）和E（G）分別表示圖的頂點集合和邊集合。對任意的ν∈V（G），我們用dG（ν）表示頂點ν在G中的度數(shù)?！鳎℅）和δ（G）分別表示圖G的最大度和最小度。對V（G）的子集S，用

2、G—S表示從G中刪去頂點集合S及其關(guān)聯(lián)的邊所得到的子圖。若S={ν}，則令G—ν=G—{ν}.對E（G）的子集X，用G—X表示從G中刪去邊集合X所得的子圖。若X={e），則G—{e}簡記為G—e.若存在V（G）的兩個不交子集X、Y，使得V（G）=X U Y，且G的所有邊均一個端點在X內(nèi)，另一個端點在Y內(nèi)，則稱G為二部圖，記為G=（X，Y，E（G））.如果｜X｜=｜Y｜，則稱G為均衡二部圖。 設(shè)g和f是定義在V（G）上的兩個整數(shù)值

3、函數(shù)，使對任意的ν∈V（G）有0≤g（ν）≤f（ν）.若日是圖G的一個支撐子圖，且滿足對任意頂點ν∈V（H），g（ν）≤dH（ν）≤f（ν），那么我們就稱H是圖G的一個（g，f）—因子。如果對任意的ν∈V（H）有g(shù)（ν）=a、f（ν）=b，則稱G的（g，f）—因子為[a，b]—因子。若a=b=k，則此時稱[a，b]—因子為k—因子，k=1時也稱1—因子為完美對集。對于圖G的一個因子，如果它同時包含G的一個哈密頓圈，我們就稱該因子為G的一

4、個哈密頓因子.圖G的頂點數(shù)｜V（G）｜我們通常稱為G的階，一般用n來表示。如果圖G的最小度δ（G）≥n/2，但對于G的任意一條邊e，δ（G—e）

5、G）有g(shù)（ν）≤dGh（ν）≤f（ν），則稱h為圖G的一個分?jǐn)?shù)（g，f）表示函數(shù)，令Ek={e：e∈E（G）且h（e）≠0}，設(shè)Gh是圖G的一個支撐子圖而且滿足E（Gk）=Eh，那么就稱Gh為G的一個分?jǐn)?shù)（g，f）—因子，稱h是Gh的表示函數(shù)。同理，我們可定義分?jǐn)?shù)[a，b]—因子、分?jǐn)?shù)k—因子和分?jǐn)?shù)哈密頓因子。 為了方便，對定義在V（G）上的任意函數(shù)f，我們記，f（S）=∑ν∈sf（ν），其中S（）V（G）。在因子理論的發(fā)展歷程

6、中，最基本的結(jié)論即1—因子存在性條件是Tutte在1947年給出來的，這一定理奠定了因子理論的基礎(chǔ)，1952，Tutte又給出了圖有f—因子的充要條件從而推廣了上述結(jié)論，接著到1970年，Lovasz又得到了圖有（g，f）—因子的一個判定準(zhǔn)則，從此，因子理論的研究開始活躍起來，大量關(guān)于因子理論的結(jié)果不斷的涌現(xiàn)出來。分?jǐn)?shù)圖論是現(xiàn)代圖論中一個新興的理論分支，它的出現(xiàn)與發(fā)展對傳統(tǒng)意義上經(jīng)典圖論的發(fā)展起到了極大的推動作用。分?jǐn)?shù)概念的引進(jìn)一方面使

7、得圖論在應(yīng)用領(lǐng)域上更為廣闊，另一方面，也使得經(jīng)典圖論在知識結(jié)構(gòu)上更加系統(tǒng)、完善。在本文中主要研究的就是哈密頓因子和分?jǐn)?shù)哈密頓因子方面的一些結(jié)果。 圖的哈密頓圈是指所包含的圈的數(shù)目為1的圖的2—因子。通過定義，顯然我們可以把一個圖G的哈密頓圈看作是G的一個包含某個哈密頓圈（實際上即為其本身）的2—因子。因此，我們很自然的要問：能否從已有的一些關(guān)于哈密頓圈存在性的充分條件出發(fā)做相應(yīng)的推廣，進(jìn)而得到一些相關(guān)或者類似的充分條件，使得在G

8、中存在包含某個（甚至任意一個）哈密頓圈這樣一種具有約束條件的特殊因子.當(dāng)然，這里所提到的這類特殊因子一般來說應(yīng)該更具一般性，比方說它可以是一個[a，b]—因子或者k—因子，也可以是一個分?jǐn)?shù)[a，b]—因子。事實上，我們在本文中主要研究的就是這樣的一些特殊因子在圖中存在的充分性條件。對哈密頓因子問題的研究，其意義主要有兩方面：一方面如上所述，它可以看作是哈密頓圈問題的推廣，因此有助于我們更加深入研究哈密頓圈問題，另一方面，研究哈密頓因子對

9、我們研究連通因子也是很有幫助的，因為如果一個圖有哈密頓因子的話，那么顯然該圖有連通因子（而且是有2—連通的連通因子）.事實上，這也是我們研究哈密頓因子問題的根本目的和出發(fā)點。 本研究共分三章：第一章簡單介紹一下圖論中的一些基本概念，并給出因子、分?jǐn)?shù)因子、哈密頓圈問題的歷史背景和進(jìn)展?fàn)顩r以及一些已有的相關(guān)結(jié)論.這一章足后面其他各章節(jié)的基礎(chǔ)。第二章我們主要討論圖的哈密頓因子的一些情況。主要結(jié)論為：定理2.1.1.設(shè)G是頂點數(shù)為n的均

10、衡二部圖，δ（G）≥n/4+1，b≥a≥2為正整數(shù)，n≥4（a+b）—23，那么對G的任一給定的哈密頓圈C，G都有一個[a，b]—因子包含C。定理2.2.1.設(shè)正整數(shù)b>a≥2，G是一個階為n≥3的簡單圖且無割邊，δ（G）≥a，若當(dāng)n為偶數(shù)時，n≥4（a+b）—20；當(dāng)n為奇數(shù)時，n≥3（a+b）—16.而且對G中任意兩個不相鄰頂點u，v，有max{dG（u），dG（v）}≥n/2+1，那么對G的任意一個給定的哈密頓圈C，G都有一個[a

11、，b]—因子包含C。定理2.3.4.設(shè)b>a≥2是一個正整數(shù)，G是一個頂點數(shù)為n的簡單圖，n≥3（a+b）—8，δ（G）≥n+1/2，那么①對G中任一給定的哈密頓圈C和邊e∈E（G），G有一個[a，b]—因子過e且包含C。②對G中任一給定的哈密頓圈C和邊e，e（）E（C），G有一個[a，b]—因子包含C但不包含e。第三章則討論了圖的分?jǐn)?shù)哈密頓[a，b]—因子的一些情況，其主要結(jié)論為：命題3.1.1.設(shè)正整數(shù)a≥1，b≥a+2，G是一個頂

12、點數(shù)為n的圖，δ（G）≥a，n≥（a+b—4）（2a+b—5）/（b—2），對任意的z，y∈V（G），max{dG（x），dG（y））≥（a—2）n/a+b—4+2，那么G有一個分?jǐn)?shù)哈密頓[a，b]—因子。定理3.2.1.設(shè)正整數(shù)b≥a≥2，G是一個圖，頂點數(shù)n≥3，δ（G）≥a，若當(dāng)n為偶數(shù)時，n≥3（a+b）—13；當(dāng)n為奇數(shù)時，n≥3（a+b）—12.而且對G中任意兩個不相鄰的頂點u，ν有max{dG（u），dG（ν））≥n/2+