不超過(guò)1的偶因子指標(biāo)

呂盛梅

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

1 預(yù)備與基本概念

本文考慮的圖均是有限無(wú)向簡(jiǎn)單圖，所有未定義的術(shù)語(yǔ)和符號(hào)參見(jiàn)文獻(xiàn)[1].

圖G的偶因子是指G的一個(gè)生成子圖并且所有點(diǎn)在這個(gè)子圖中的度均是偶數(shù)。一個(gè)至少有3個(gè)點(diǎn)且每個(gè)點(diǎn)的度數(shù)都是偶數(shù)的連通圖稱為閉跡。圖G有一個(gè)k-控制系是指G有一個(gè)子圖H，它是由k個(gè)邊不交的閉跡和星(K1,s，s≥3)構(gòu)成，并且使得G的每條邊或者屬于閉跡或星，或者與閉跡的某條邊鄰接。如果G的偶因子中每個(gè)點(diǎn)的度均為2，那么稱這個(gè)偶因子為G的2-因子。含有一個(gè)連通的2-因子的圖稱為哈密爾頓圖。圖G的哈密爾頓指標(biāo)(或2-因子指標(biāo)，或偶因子指標(biāo))分別是指使得Ln(G)含有一個(gè)哈密爾頓圈(或一個(gè)2-因子，或一個(gè)偶因子)的最小的整數(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)部頂點(diǎn)均在V2(G)中且端點(diǎn)在W(G)中。如果一條枝的長(zhǎng)度為1，那么它沒(méi)有內(nèi)點(diǎn)。用B(G)表示G中所有的枝的集合。記B1(G)={b∈B(G)∶V(b)IV1(b)≠φ}.對(duì)于任意一個(gè)B(G)中的子集S，用G-S表示從圖G中刪掉S的每一條枝的所有內(nèi)部頂點(diǎn)后所得到的一個(gè)子圖。如果子圖G-S的分支多于圖G的分支，那么就稱S為枝割。一個(gè)最小的枝割稱為圖G的枝鍵。用BB(G)表示圖G的所有枝鍵的集合。對(duì)于連通圖G，一個(gè)枝鍵S是指使得G-S不連通的最小的枝集的子集。很容易證明，連通圖G中B(G)的子集S是枝鍵當(dāng)且僅當(dāng)G-S恰好有兩個(gè)分支。如果一個(gè)枝鍵是由奇數(shù)條枝組成的，那么稱這個(gè)枝鍵是奇枝鍵。一個(gè)枝鍵S的長(zhǎng)度是指S中最短的枝的長(zhǎng)度，即這條最短的枝的邊數(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-因子指標(biāo)，并且得到如下結(jié)論：

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

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

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

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

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

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

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

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

2 主要結(jié)果

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

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

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

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

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

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

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

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

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

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

證明：先證“充分性”。因?yàn)閔1(G)=1，所以G中至少存在1條邊，它的一個(gè)端點(diǎn)的度為1，顯然圖G本身沒(méi)有2-因子。則f(G)≥1.假設(shè)G有一個(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有一個(gè)k-控制系。所以，定理得證。

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

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

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

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

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

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

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

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

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

證明：先證“充分性”。因?yàn)镚是一個(gè)無(wú)爪圖并且δ(G)≥2，所以h1(G)=0.又因?yàn)槊總€(gè)奇枝鍵都包含一個(gè)長(zhǎng)為1的枝，則h2(G)=1.于是有β(G)=max{h1(G),h2(G)-1}=0.再由引理4，就有ef(G)=β(G)=0.

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

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

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

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

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

在引理7中，因?yàn)閳DG有橋且δ(G)≥3，則h1(G)=0且h2(G)=1.所以，β(G)=0.于是，得到另一個(gè)結(jié)論：

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