胡 琳

(新疆大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院， 新疆 烏魯木齊 830017)

0 引言

本文中我們只考慮有限的無(wú)向簡(jiǎn)單圖,對(duì)于未定義的符號(hào)與術(shù)語(yǔ)請(qǐng)參見(jiàn)文獻(xiàn)[1].令G=(V,E)是一個(gè)圖，頂點(diǎn)數(shù)記為|V|.對(duì)于任意頂點(diǎn)v∈V(G),用N(v)表示其鄰點(diǎn)集合，即{u:uv∈E(G)}.v的度dG(v)(或簡(jiǎn)記為d(v))是指在G中與v相鄰的邊的條數(shù).由于G是一個(gè)簡(jiǎn)單圖，故d(v)=|N(v)|.集合S?V的開(kāi)鄰集即N(S)=∪v∈SN(v).G中的最小度與最大度分別用δ(G)和Δ(G)來(lái)表示.一個(gè)圖稱(chēng)為k-正則的，如果Δ(G)=δ(G)=k.特別地，3-正則圖也被稱(chēng)為立方圖.此外，如果Δ(G)≤3,我們稱(chēng)G是準(zhǔn)立方圖.用c(G)表示圖G的分支個(gè)數(shù).

若V(G)=X∪Y,這里X∩Y=?,|X|=m,|Y|=n,且?e∈E(G),有e=xy,其中x∈X,y∈Y,我們稱(chēng)這類(lèi)圖為二部圖，記為G=(X,Y;E).特別地，若X中的任一頂點(diǎn)與Y中任一頂點(diǎn)均有唯一的邊相鄰，則G為完全二部圖，記為Km,n,當(dāng)m=1時(shí)，稱(chēng)為n-star.如果圖G中不含有同構(gòu)于K1,3的導(dǎo)出子圖，則稱(chēng)圖G是無(wú)爪圖，也稱(chēng)圖K1,3是G的禁止子圖.

如果V(H)=V(G),G的子圖H稱(chēng)為生成子圖.特別地，若H是G的生成子圖且對(duì)于任意v∈V(H)均有dH(v)≥1,則H是G的一個(gè)因子.設(shè)f是定義在V(G)上的正整數(shù)值函數(shù)，若因子H中任一點(diǎn)v,均有dH(v)=f(v),則稱(chēng)H是G的一個(gè)f-因子.特別地，f的值均為偶數(shù)的生成子圖稱(chēng)為G的一個(gè)偶因子.若偶因子中頂點(diǎn)度均為2，則是G的一個(gè)2-因子.集合S?V(G),G[S]定義為以S為頂點(diǎn)集合，其中兩點(diǎn)相鄰當(dāng)且僅當(dāng)它們?cè)贕中相鄰的圖.

稱(chēng)對(duì)G進(jìn)行若干次刪點(diǎn)、刪邊和縮邊后所得的圖H是G的一個(gè)minor.

下面是Petersen的一個(gè)經(jīng)典定理[2].

定理1每個(gè)2r-正則圖可以分解為r個(gè)邊不相交的2-因子；每個(gè)無(wú)割邊的立方圖都包含一個(gè)完美匹配.

Tutte定理刻畫(huà)了一類(lèi)具有完美匹配或f-因子的圖.Edmonds[3]第一次給出了圖中尋找最大匹配的多項(xiàng)式時(shí)間算法，它也適用于尋找2-因子或f-因子.

李學(xué)良等[4]給出了不含有偶因子的圖.

定理2令G是連通圖，若G不包含偶因子，則存在子集S?V(G),使得

(i)S是獨(dú)立集；

(iii)G-S的每個(gè)分支C,連接C與S的邊數(shù)是奇數(shù).

與此同時(shí)，他們還證明了下面的推論.

推論1若G是至多包含兩個(gè)2度點(diǎn)，其余點(diǎn)度數(shù)至少是3的2-邊連通圖，則其包含一個(gè)偶因子.

通過(guò)給出的線圖中的禁止子圖[5]，康麗英等[6-7]得到了下面結(jié)論.

Funk等[8]最早提出，稱(chēng)一個(gè)圖G是2-因子Hamiltonian的，如果其每個(gè)2-因子都是Hamilton圈.

定理4設(shè)G是2-因子Hamiltonian的k-正則二部圖，則k≤3.

Diwan[9]證明了一個(gè)平面多重立方圖G是2-因子Hamiltonian的，當(dāng)且僅當(dāng)或者G≌K4或者G與三條平行邊連接兩個(gè)頂點(diǎn)的圖同構(gòu).Abreu等[10]提出了至今依舊未解決的下面這個(gè)有趣的猜想.

猜想1 一個(gè)4-正則圖是2-因子Hamiltonian的，當(dāng)且僅當(dāng)G≌K5.

本文中，我們將證明上述猜想對(duì)于包含一個(gè)K4的無(wú)爪4-正則圖成立.

1 預(yù)備工作

眾所周知，對(duì)于任意圖G,有κ(G)≤κ′(G)≤δ(G),并且若Δ(G)≤3,則κ(G)=κ′(G).

引理1G是連通的立方圖，v∈V(H).如果κ′(H-v)=2并且H-v不包含2-因子，則在H-v中存在一個(gè)獨(dú)立集S,使得

(i)c(H-v-S)=|S|-1,并且e(C,S)=3對(duì)G-S的每個(gè)分支C均成立；

(ii)NH(v)?S.

證明令H′=H-v.由于H′中不含有偶因子，由定理2，H′中存在獨(dú)立集S,滿(mǎn)足

(ii)對(duì)H′-S的每個(gè)分支C'都有eH′(C',S) 是奇數(shù).

設(shè)V2是H′中度為2的點(diǎn)的集合，即V2=NH(v).另一方面，我們有

(1)

另一方面

(2)

立方圖中去掉一個(gè)頂點(diǎn)的圖稱(chēng)為近似立方圖.由定義，一個(gè)近似立方圖是恰含三個(gè)2度點(diǎn)的子立方圖.

推論2設(shè)H是3-連通立方圖，V∈V(H).如果H-v不包含同構(gòu)于二部立方圖去掉一個(gè)頂點(diǎn)的minor，則H-v包含一個(gè)2-因子.

證明假設(shè)H-v不含2-因子.因?yàn)镠-v是2-連通的，由引理1,存在H-v的獨(dú)立集S滿(mǎn)足

(i)H-v-S中恰有|S|-1個(gè)分支，并且對(duì)G-S的每個(gè)分支C均有e(C,S)=3；

(ii)NH(v)?S.

通過(guò)對(duì)H-v-S的每個(gè)非平凡分支C的收縮，我們可以得到一個(gè)二部立方圖H′去掉一個(gè)頂點(diǎn)，矛盾.因此H-v包含一個(gè)2-因子.

推論3任意3-連通立方圖G與其中一頂點(diǎn)v∈V(G),G-v可以被分解成一些3-star與一些包含2-因子的2-連通近似立方圖的并.

證明此證明對(duì)G的頂點(diǎn)數(shù)n做歸納.當(dāng)n=4,則G≌K4,從而G-v≌K3,顯然G-v本身是一個(gè)2-因子.

假設(shè)n≥6,且結(jié)論對(duì)于所有頂點(diǎn)個(gè)數(shù)小于n的3-連通立方圖和每個(gè)頂點(diǎn)v∈V(G)均成立.我們進(jìn)一步假設(shè)G-v本身不含有2-因子,也就是說(shuō)，由于Δ(G-v)≤3,它不包含偶因子.由引理1，G-v中存在一個(gè)獨(dú)立集，使得

(i)G-v-S恰含|S|-1個(gè)分支, 對(duì)G-S的每個(gè)分支C都有e(C,S)=3；

(ii)V2?S.

根據(jù)以上討論，我們選取滿(mǎn)足條件且|S|最大的集合S.由(i)可知G-v-S的每個(gè)非平凡分支C是一個(gè)近似立方圖.又G是3-連通的，故G-v-S的每個(gè)非平凡分支C一定是2-連通的近似立方圖.此外，對(duì)于G-S的一個(gè)非平凡分支，令C*是通過(guò)添加新的頂點(diǎn)v并將其與C的三個(gè)2度點(diǎn)相連而得到的圖.從而C*是3-連通的.否則，存在C*的一個(gè)2-點(diǎn)割T必定包含v,因此T中另一個(gè)點(diǎn)成為C的一個(gè)割點(diǎn)，矛盾.

通過(guò)歸納假設(shè)，G-S的每個(gè)非平凡分支C可以被分解成一些3-star與一些包含2-因子的2-連通近似立方圖的并.另一方面，由于與S中的點(diǎn)相鄰的邊均被分解成中心在S的3-star.因此，G可以被分解成一些3-star和一些包含2-因子的2-連通近似立方圖的并.

引理2頂點(diǎn)個(gè)數(shù)n≥6的4-正則圖G,以下結(jié)論成立:

(i)κ′(G)∈{2,4}；

(ii)若κ′(G)=2,則G有一個(gè)不連通的2-因子.

證明：因?yàn)镚是偶圖，從而每一個(gè)邊割均是偶的，也就是說(shuō)κ′(G)∈{0,2,4}.同時(shí)，由G是連通圖，即κ′(G)≥1.結(jié)論(i)成立.由定理1，G含有一個(gè)2-因子F.如果F不連通，則結(jié)論成立.因此假設(shè)F是一個(gè)Hamilton圈.由假設(shè)(ii)，設(shè)E′={e1,e2}是G的一個(gè)2-邊割.顯然有E′?E(F),否則與F的Hamilton性相矛盾.從而可知G?E(F)是一個(gè)不連通的2-因子.

2 主要結(jié)果

引理3任意二部立方圖H,L(H) 包含一個(gè)不連通的2-因子.

證明設(shè)H是一個(gè)二部圖，頂點(diǎn)集為(X,Y),G=L(H).顯然,對(duì)于頂點(diǎn)x,G[E(x)] 是一個(gè)三角形，這里E(x)是指在H中與x相鄰的邊集.因此，{G[E(x)]:x∈X} 是一個(gè)每個(gè)分支都是一個(gè)三角形的不連通2-因子.

情形1當(dāng)k≥2時(shí),n=3k.

情形2當(dāng)k≥2時(shí),n=3k+1.

情形3當(dāng)k≥2時(shí),n=3k+2.

定理5若H是立方圖，則G=L(H)包含一個(gè)不連通的2-因子.

證明容易看出，若H包含一個(gè)不連通的2-因子，則G也含有一個(gè)不連通的2-因子. 因此，假定H是2-因子Hamiltonian的.容易證明κ(G)=3.取頂點(diǎn)v∈V(H)使得κ′(H-v)=2.由推論3，H-v可以被分解成一些3-star與一些含有2-因子的近似立方圖.從而可得L(H)包含一個(gè)不連通的2-因子.

定理6若G是頂點(diǎn)個(gè)數(shù)n≥6且包含K4的4-正則圖，則G中存在一個(gè)不連通的2-因子.

證明由定理1，G包含一個(gè)2-因子C.如果C是不連通的，則結(jié)論成立.因此，假設(shè)C是連通的，即，C是G的一個(gè)Hamilton圈.

情形1n是偶數(shù).

對(duì)每個(gè)i∈{1,2,3,4},令xi′∈V(G)〗{x1,x2,x3,x4}為xi在G中的鄰點(diǎn).若x2′=x3′,則x2,x2′,x3,x1,x4,x2是G〗E(C)中的一個(gè)5圈，也就是說(shuō),G〗E(C)是G的一個(gè)不連通2-因子.因此，假設(shè)x2'≠x3',令M是C中包含x2x3的一個(gè)完美匹配.我們考慮立方圖G〗M.如果G〗M包含一個(gè)不連通的2-因子，結(jié)論成立.令M*是G〗E(C)中包含{x2x2′,x3x3′,x1x4}的一個(gè)完美匹配.從而G〗(M∪M*)是G中包含一個(gè)同構(gòu)于C4的分支x1,x2,x4,x3,x1的完美匹配.

情形2n是奇數(shù).

假設(shè)G中不存在兩個(gè)點(diǎn)不交的4-團(tuán).否則，令S1,S2?V(G)滿(mǎn)足S1∩S2=?且對(duì)每個(gè)i∈{1,2}均有G[Si]≌K4.設(shè)G′=G/S1即G收縮S1.易得G'是包含一個(gè)K4且頂點(diǎn)個(gè)數(shù)是偶數(shù)的4-正則圖.根據(jù)情形1，G'包含一個(gè)不連通的2-因子.取G'的一個(gè)頂點(diǎn)s,Cs是G中不連通分支C'中的一個(gè)圈.不妨設(shè)s1與s2是s在C′s上的兩個(gè)鄰點(diǎn).不失一般性，對(duì)每個(gè)i,令si是xi∈S1的鄰點(diǎn).在Cs′中用s1x1x3x4x2s2替換s1ss2,可得G中的一個(gè)圈Cs.在C'中用Cs代替Cs′,即可得G中的一個(gè)不連通的2-因子.

因此，假設(shè)S?V(G)滿(mǎn)足G[S]≌K4.注意到G/S是4-正則圖.如果G/S是二部圖，由定理4可得其中存在一個(gè)不連通的2-因子.從而G中亦包含一個(gè)不連通的2因子.因此我們假設(shè)G/S不是二部圖，所以G0=GS也不是二部圖.

情形2.1|N(S)S|=4.

情形2.2|N(S)〗S|=3.

S中的兩個(gè)頂點(diǎn)在V(G)S有共同的鄰點(diǎn)x,其余兩個(gè)頂點(diǎn)在V(G)S中有兩個(gè)鄰點(diǎn).若x的鄰點(diǎn)為x2,x3,與情形1類(lèi)似，GE(C)是G的一個(gè)不連通2-因子.否則，可以假設(shè)x1,x2的公共鄰點(diǎn)是x,即x=xn.如果x3x6∈E(G),那么存在C的一個(gè)匹配M0不包含x5,x6和xn.因此，由推論1可得G0M0包含一個(gè)2-因子.否則，C的一個(gè)最大匹配M0在G0中不包含xn.考慮圖G'0=G0M0,它是一個(gè)非二部圖的近似立方圖.根據(jù)推論2可得G'0包含一個(gè)2-因子，從而G包含一個(gè)不連通的2-因子.

情形2.3|N(S)〗S|=2.

S中的所有頂點(diǎn)在V(G)S有兩個(gè)公共的鄰點(diǎn)x5,xn.如果x2,x3在V(G)S公共鄰點(diǎn)，則G〗E(C)即為G的一個(gè)不連通2-因子.因而我們假設(shè)x2xn與x3x5都在E(G)中.

令S1={x1,x2,x3,x4,x5,xn}.類(lèi)似于情形2.1與情形2.2的討論，如果|N(S1)|=4或是|N(S1)|=3,設(shè)G1=G〗S1,則C中存在一個(gè)不包含x6或xn-1的最大匹配M1.考慮圖G'1=G1M1,它是一個(gè)非二部圖的近似立方圖，根據(jù)推論2，其中存在一個(gè)2-因子.從而G包含一個(gè)不連通2-因子，其中一個(gè)分支是x1,x3,x5,x4,x2,xn,x1；或者G〗E(C)即為G的一個(gè)不連通2-因子.

否則,|N(S1)|=2,也就是說(shuō)x5,xn在V(G)〗S1中僅有兩個(gè)鄰點(diǎn)x6和xn-1.令S2=S1∪{x6,xn-1}.如果|N(S2)|=4或者|N(S2)|=3,我們可以得到一個(gè)不連通2-因子，其中一個(gè)分支是x1,x2,x3,x4,x1,另一個(gè)分支為x5,xn-1,xn,x6,x5；或者G〗E(C)即為G的一個(gè)不連通2-因子.

與以上討論相同，對(duì)i≥1,若|N(Si)|=4或|N(Si)|=3,G中存在一個(gè)不連通的2-因子，其中一個(gè)分支是x1,x3,x5,x4,x2,xn,當(dāng)i是奇數(shù)時(shí)；或是x1,x2,x3,x4,x1,當(dāng)i是偶數(shù)時(shí).反之，|N(Si)|=2,我們可以構(gòu)造Si+1.由于n是一個(gè)奇數(shù)，每次添加兩個(gè)點(diǎn)到Si,因而存在i*,使得|N(Si*)|≥3.此時(shí)，通過(guò)情形2.1與情形2.2的相同的證明我們即可以得到G的一個(gè)不連通2-因子.

推論4頂點(diǎn)個(gè)數(shù)至少是6的4-正則無(wú)爪圖包含一個(gè)不連通的2-因子.