不含相鄰三角形的平面圖的線性 2-蔭度＊

盛慧玉

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院,浙江金華 321004)

0 引 言

本文僅考慮簡單有限無向圖.對于一個圖 G,分別用 V(G),E(G),Δ(G),δ(G)表示點(diǎn)集、邊集、最大度和最小度.k-點(diǎn)表示度是 k的頂點(diǎn),k+-點(diǎn)表示度至少是 k的頂點(diǎn).「x┒表示不小于實數(shù) x的最小整數(shù),┖x」表示不大于實數(shù) x的最大整數(shù).一個圖 G的邊劃分是指將 G分解成子圖 G1,G2,…,Gm,使得E(G)=E(G1)∪E(G2)∪…∪E(Gm)且 E(Gi)∩E(Gj)=?(i≠j);線性 k-森林是指一個圖 G,它的每個連通分支是長至多為 k的路;圖 G的線性 k-蔭度是指使得 G可以邊劃分成 m個線性 k-森林的最小整數(shù)m,用 lak(G)表示.顯然,當(dāng) k≥1時,lak(G)≥lak+1(G).特別地,la1(G)就是 G的通常邊色數(shù)χ′(G);la∞(G)表示每個分支路均為無限長的情況,也就是 G的線性蔭度 la(G).

圖的線性 k-蔭度最早由 Habib和 Péroche引進(jìn),文獻(xiàn) [1-3]對此作了深入的研究;圈、樹、完全圖及完全二部圖的線性 2-蔭度在文獻(xiàn) [1,4]中進(jìn)行了討論;文獻(xiàn) [5]證明了當(dāng) k≥5時,對于 3-正則圖 G有l(wèi)ak(G)≤2,而且該結(jié)果是最好的.關(guān)于線性蔭度的一個著名猜想由 Akiyama[6]提出:對于每一個簡單圖面圖,文獻(xiàn)[10-11]證明了該猜想成立.

1 幾個引理

引理 1 設(shè) G是不含相鄰三角形且δ(G)≥2的平面圖,則以下 2個結(jié)論中必有 1個成立:存在邊xy∈E(G),使得 dG(x)+dG(y)≤11;存在 2-交錯圈 v1v2…v2sv1,使得 d(v1)=d(v3)=…=d(v2s-1)=2.

證明 假設(shè)均不成立,則以下斷言成立:

斷言 1 ?xy∈E(G),滿足 dG(x)+dG(y)≥12,從而 2-點(diǎn)的鄰點(diǎn)一定是 10+-點(diǎn),3-點(diǎn)的鄰點(diǎn)一定是9+-點(diǎn).

斷言 2 設(shè) G2是 G中 2-點(diǎn)關(guān)聯(lián)的邊生成的子圖,則 G2是森林.

由假設(shè)不成立可知,G2不含偶圈,由斷言 1知,G中任意 2個 2-點(diǎn)不相鄰,從而 G2中也不含奇圈,所以 G2是森林.

斷言 3 G2包含一個匹配M,使得M飽含 G中的所有 2-點(diǎn).

假設(shè) G中的頂點(diǎn)和面已被賦權(quán),即當(dāng) x∈V(G)∪E(G)時,初始權(quán) ch(x)=d(x)-4,ch＊(x)表示最終權(quán).

權(quán)轉(zhuǎn)移規(guī)則如下 (見圖 1):

R1:每個 2-點(diǎn)從 2-master得權(quán) 2.

3)若 3-面關(guān)聯(lián)均為 5+-點(diǎn),則 3個點(diǎn)分別

圖 1 權(quán)轉(zhuǎn)移規(guī)則

驗證新權(quán):

下面通過 2個斷言證明?x∈V∪F,有 ch＊(x)≥0.

斷言 4 ?f∈F(G),ch＊(f)≥0.

當(dāng) f是 3-面時,根據(jù) R3,可以接受其相關(guān)聯(lián)的 2個或 3個點(diǎn)的權(quán)共 1,則 ch＊(f)≥0.

當(dāng) f是 4+-面時,f既不接受權(quán),也不轉(zhuǎn)出權(quán),故 ch＊(f)=ch(f)≥0.

斷言 5 ?v∈V(G),ch＊(v)≥0.

當(dāng) v是 2-點(diǎn)時,根據(jù) R1,它的 2-master給它權(quán) 2,故 ch＊(v)=-2+2=0.

當(dāng) v是 10+-點(diǎn)時,分 2種情況討論:

證明 對 |V(G)|+|E(G)|用數(shù)學(xué)歸納法.當(dāng) |V(G)|+|E(G)|≤5時,結(jié)論顯然成立.當(dāng) |V(G)|+|E(G)|≥6且Δ(G)≤6時,只要令 F1=F2=?,H=G即滿足引理 2條件.

如果δ(G)≥2,由引理 1,只需考慮 2種情況.

1)存在邊 xy∈E(G),使得 dG(x)+dG(y)≤11.

2 主要結(jié)果

證明

定理 1證畢.

[1]Aldred R E L,Wormald N C.More on the lineark-arboricity of regular graphs[J].Australas J Comb,1998,18(1):97-104.

[2]Be rmond J C,Fouquet J L,HabibM,et al.On lineark-arboricity[J].DiscreteMath,1984,52(2/3):123-232.

[3]Jackson B,Wormald N C.On the lineark-arboricity of cubic graphs[J].DiscreteMath,1996,162(1/2/3):293-297.

[4]HabibM,Pèroche P.Some problems about linear arboricity[J].DiscreteMath,1982,41(2):219-220.

[5]Thomassen C.Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5[J].J Comb Theroy Ser:B,1999,75(1):100-109.

[6]Akiyama J.Three developing topics in graph theory[D].Tokyo:University of Tokyo,1980.

[7]Akiyama J,Exoo G,Harary F.Covering and packing in graphsⅢ:Cyclic and acyclic invariants[J].Math Slovaca,1980,30(4):405-417.

[8]Enomoto H,Pèerche B.The linear arboricity of some regular graphs[J].J Graph Theory,1984,8(2):309-324.

[9]Guldan F.The linear arboricity of 10-regular graphs[J].Math Slovaca,1986,36(3):225-228.

[10]Wu Jianliang.On the linear arboricity of planar graphs[J].J Graph Theory,1999,31(2):129-134.

[11]Wu Jianliang,Wu Yuwen.The linear arboricityofplanar graphsofmaximum degree seven is four[J].J Graph Theory,2008,58(3):210-220.

[12]Lik KW,TongLida,WangWeifan.The linear 2-arboricity of planar graphs[J].Graphs Comb,2003,19(2):241-248.

[13]孫向勇,吳建良.特殊平面圖的線性二蔭度[J].山東師范大學(xué)學(xué)報:自然科學(xué)版,2007,22(3):9-13.

[14]Chen B L,Fu H L,Huang K C.Decomposing graphs into forests of pathswith size less than three[J].Australas J Comb,1991,3(1):55-73.

(責(zé)任編輯 陶立方)