不超過1的偶因子指標

呂盛梅

(青海民族大學 數(shù)學與統(tǒng)計學院，西寧 810007)

1 預備與基本概念

本文考慮的圖均是有限無向簡單圖，所有未定義的術(shù)語和符號參見文獻[1].

圖G的偶因子是指G的一個生成子圖并且所有點在這個子圖中的度均是偶數(shù)。一個至少有3個點且每個點的度數(shù)都是偶數(shù)的連通圖稱為閉跡。圖G有一個k-控制系是指G有一個子圖H，它是由k個邊不交的閉跡和星(K1,s，s≥3)構(gòu)成，并且使得G的每條邊或者屬于閉跡或星，或者與閉跡的某條邊鄰接。如果G的偶因子中每個點的度均為2，那么稱這個偶因子為G的2-因子。含有一個連通的2-因子的圖稱為哈密爾頓圖。圖G的哈密爾頓指標(或2-因子指標，或偶因子指標)分別是指使得Ln(G)含有一個哈密爾頓圈(或一個2-因子，或一個偶因子)的最小的整數(shù)n，分別記為h(G)(或f(G)，或ef(G)).

記Vi(G)={v∈V(G)∶dG(v)=i}和W(G)=V(G)V2(G).圖G中的一條路叫做枝是指它的內(nèi)部頂點均在V2(G)中且端點在W(G)中。如果一條枝的長度為1，那么它沒有內(nèi)點。用B(G)表示G中所有的枝的集合。記B1(G)={b∈B(G)∶V(b)IV1(b)≠φ}.對于任意一個B(G)中的子集S，用G-S表示從圖G中刪掉S的每一條枝的所有內(nèi)部頂點后所得到的一個子圖。如果子圖G-S的分支多于圖G的分支，那么就稱S為枝割。一個最小的枝割稱為圖G的枝鍵。用BB(G)表示圖G的所有枝鍵的集合。對于連通圖G，一個枝鍵S是指使得G-S不連通的最小的枝集的子集。很容易證明，連通圖G中B(G)的子集S是枝鍵當且僅當G-S恰好有兩個分支。如果一個枝鍵是由奇數(shù)條枝組成的，那么稱這個枝鍵是奇枝鍵。一個枝鍵S的長度是指S中最短的枝的長度，即這條最短的枝的邊數(shù)，記為l(S).

記BB1(G)=B1(G)，BB2(G)={S∈BB(G)BB1(G)∶S是奇的}，那么定義hi(G)，i=1,2如下：

2007年，XIONG et al[2]研究了圖的2-因子指標，并且得到如下結(jié)論：

定理1[2]設(shè)G是一個連通圖，但不是一條路，則

f(G)≥max{h1(G),h2(G)-1} .

如果令β(G)=max{h1(G),h2(G)-1}，那么有結(jié)論：

定理2[2]設(shè)G是一個滿足β(G)≥2的連通圖，但不是一條路，則f(G)=β(G).

定理3[2]設(shè)G是一個滿足β(G)≤1的圖，但不是一條路，則f(G)≤2.

在文獻[3]中，F(xiàn)UJISAWA et al得到一個結(jié)果：

定理4[3]設(shè)G是一個滿足β(G)=0的圖，但不是一條路，則f(G)≤1.

從上面的結(jié)果中可以看出，當β(G)取不同的值時，圖G的2-因子指標f(G)的取值也各不相同。從定理3和定理4中觀察發(fā)現(xiàn)，當β(G)取值較小時(不超過1)，f(G)的值也比較小。在這個發(fā)現(xiàn)的鼓勵下，考慮了這樣一些問題：哪些圖能夠滿足f(G)=β(G)≤1?哪些圖的偶因子指標ef(G)=0？并且得到了一些相關(guān)的結(jié)論。

2 主要結(jié)果

首先，考慮了滿足f(G)=β(G)=0的圖的結(jié)構(gòu)，并得到了以下結(jié)論：

定理5 設(shè)G是一個滿足h1(G)=0的圖，并且從G中刪除所有的鍵后得到的那個圖的每個非平凡的分支均是哈密爾頓圖，則f(G)=β(G)=0.

證明：“從G中刪除所有的鍵后得到的那個圖的每個非平凡的分支均是哈密爾頓圖”意味著h2(G)=1并且由此得到的每個非平凡的分支都包含了一個哈密爾頓圈，即G的一個2-因子分支。顯然圖G包含一個2-因子，即f(G)=0.又因為h1(G)=0，那么β(G)=max{h1(G),h2(G)-1}=0=f(G).定理得證。

接下來，考慮了關(guān)于f(G)=β(G)=1的情形。在給出結(jié)論之前，先給出幾個相關(guān)引理：

引理3[5]設(shè)G是至少有3條邊的簡單連通圖。則f(G)≤1當且僅當G有一個k-控制系，其中k是某個正整數(shù)。

在引理1和引理2中，G的每個奇枝鍵中最短的枝長度均為2意味著h2(G)=2.而在引理1中每個1度點都有一個度至少為3的鄰點意味著h1(G)=1.則β(G)=max{h1(G),h2(G)-1}=1.在引理2中δ(G)≥2意味著h1(G)=0.則也有β(G)=0.然而滿足引理1或引理2的圖G本身沒有2-因子，即f(G)≥1，因為奇枝鍵中最短的枝長度均為2說明總有一個點(最短的枝的內(nèi)點)是不能屬于任何2-因子分支的，并且引理1中存在1度點，它也是無法屬于任何2-因子的。于是，我們得到與引理1和引理2相應(yīng)的兩個結(jié)論：

定理6 設(shè)G是一個至少有4個頂點的簡單圖且每個1度點都有一個度至少為3的鄰點。如果G的每個奇枝鍵中最短的枝長度均為2，則f(G)=β(G)=1.

定理7 設(shè)G是一個至少有4個頂點的簡單圖且δ(G)≥2.如果G的每個奇枝鍵中最短的枝長度均為2，則f(G)=β(G)=1.

在引理3的基礎(chǔ)上，我們得到下面結(jié)論：

定理8 設(shè)G是一個至少有3條邊的簡單連通圖且h1(G)=1.則f(G)=β(G)=1當且僅當G有一個k-控制系，其中k是某個正整數(shù)。

證明：先證“充分性”。因為h1(G)=1，所以G中至少存在1條邊，它的一個端點的度為1，顯然圖G本身沒有2-因子。則f(G)≥1.假設(shè)G有一個k-控制系，由引理3，f(G)≤1.于是f(G)=1.再由k-控制系的結(jié)構(gòu)可知：h2(G)≤2，則β(G)=max{h1(G),h2(G)-1}=1.所以，f(G)=β(G)=1.

再證“必要性”。已知f(G)=β(G)=1，則由引理3可得，G有一個k-控制系。所以，定理得證。

最后，考慮圖G的偶因子指標。在文獻[6]中，熊黎明得到這樣一個結(jié)論：

定理9[6]設(shè)G是一個簡單圖但不是一條路。如果β(G)≥1，則ef(G)=β(G).

這個定理意味著對于所有β(G)≥1的簡單圖，其偶因子指標也必大于等于1.因此，考慮ef(G)=β(G)=0的圖是我們比較感興趣的。我們先給出一些引理如下：

引理4[6]設(shè)G是一個無爪圖。則G有一個偶因子當且僅當δ(G)≥2并且G的每個奇枝鍵都包含一個長為1的枝。

引理5[6]每個δ(G)≥3的無爪圖都有一個偶因子。

引理6[7]每個δ(G)≥3的無橋簡單圖G都有一個偶因子，并且偶因子的每個分支都至少有4個頂點。

引理7[7]設(shè)G是一個δ(G)≥3的簡單圖。如果圖G的所有橋都在G的同一條路上，則G有一個偶因子且它的每個分支都至少有4個頂點。

下面給出得到的結(jié)論：

定理10 設(shè)G是一個無爪圖。則ef(G)=β(G)=0當且僅當δ(G)≥2并且G的每個奇枝鍵都包含一個長為1的枝。

證明：先證“充分性”。因為G是一個無爪圖并且δ(G)≥2，所以h1(G)=0.又因為每個奇枝鍵都包含一個長為1的枝，則h2(G)=1.于是有β(G)=max{h1(G),h2(G)-1}=0.再由引理4，就有ef(G)=β(G)=0.

再證“必要性”。因為ef(G)=0意味著圖G有一個偶因子，則δ(G)≥2.已知β(G)=0，則有h1(G)=0且h2(G)≤1.若G不包含任何奇枝鍵，則h2(G)=0.若G中至少存在一個奇枝鍵且h2(G)=1，則這個奇枝鍵一定包含一個長為1的枝。所以，定理得證。

定理11 設(shè)G是一個無爪圖且δ(G)≥3.則ef(G)=β(G)=0.

證明：因為G是無爪圖且δ(G)≥3，則得到h1(G)=0且h2(G)≤1.于是，β(G)=max{h1(G),h2(G)-1}=0.再由引理5，即可得到ef(G)=β(G)=0.所以，定理得證。

因為δ(G)≥3，則h1(G)=0且h2(G)≤1.于是，β(G)=0.再由引理6，可以得到如下結(jié)論：

定理12 設(shè)G是一個無橋簡單圖且δ(G)≥3.則ef(G)=β(G)=0.

在引理7中，因為圖G有橋且δ(G)≥3，則h1(G)=0且h2(G)=1.所以，β(G)=0.于是，得到另一個結(jié)論：

定理13 設(shè)G是一個δ(G)≥3的簡單圖。如果圖G的所有橋都在G的同一條路上，則ef(G)=β(G)=0.