4-正則圖中的不連通2-因子

胡 琳

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

0 引言

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

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

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

稱對G進(jìn)行若干次刪點、刪邊和縮邊后所得的圖H是G的一個minor.

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

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

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

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

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

(i)S是獨立集；

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

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

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

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

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

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

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

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

本文中，我們將證明上述猜想對于包含一個K4的無爪4-正則圖成立.

1 預(yù)備工作

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

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

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

(ii)NH(v)?S.

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

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

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

(1)

另一方面

(2)

立方圖中去掉一個頂點的圖稱為近似立方圖.由定義，一個近似立方圖是恰含三個2度點的子立方圖.

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

證明假設(shè)H-v不含2-因子.因為H-v是2-連通的，由引理1,存在H-v的獨立集S滿足

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

(ii)NH(v)?S.

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

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

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

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

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

(ii)V2?S.

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

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

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

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

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

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

2 主要結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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