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

盛慧玉

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

0 引 言

本文僅考慮簡單有限無向圖.對于一個圖 G,分別用 V(G),E(G),Δ(G),δ(G)表示點集、邊集、最大度和最小度.k-點表示度是 k的頂點,k+-點表示度至少是 k的頂點.「x┒表示不小于實數 x的最小整數,┖x」表示不大于實數 x的最大整數.一個圖 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-森林的最小整數m,用 lak(G)表示.顯然,當 k≥1時,lak(G)≥lak+1(G).特別地,la1(G)就是 G的通常邊色數χ′(G);la∞(G)表示每個分支路均為無限長的情況,也就是 G的線性蔭度 la(G).

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

1 幾個引理

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

證明 假設均不成立,則以下斷言成立:

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

斷言 2 設 G2是 G中 2-點關聯的邊生成的子圖,則 G2是森林.

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

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

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

權轉移規則如下 (見圖 1):

R1:每個 2-點從 2-master得權 2.

3)若 3-面關聯均為 5+-點,則 3個點分別

圖 1 權轉移規則

驗證新權:

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

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

當 f是 3-面時,根據 R3,可以接受其相關聯的 2個或 3個點的權共 1,則 ch＊(f)≥0.

當 f是 4+-面時,f既不接受權,也不轉出權,故 ch＊(f)=ch(f)≥0.

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

當 v是 2-點時,根據 R1,它的 2-master給它權 2,故 ch＊(v)=-2+2=0.

當 v是 10+-點時,分 2種情況討論:

證明 對 |V(G)|+|E(G)|用數學歸納法.當 |V(G)|+|E(G)|≤5時,結論顯然成立.當 |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 主要結果

證明

定理 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].山東師范大學學報:自然科學版,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.

(責任編輯 陶立方)