盛慧玉

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

0 引 言

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

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

1 幾個(gè)引理

引理 1 設(shè) G是不含相鄰三角形且δ(G)≥2的平面圖,則以下 2個(gè)結(jié)論中必有 1個(gè)成立:存在邊xy∈E(G),使得 dG(x)+dG(y)≤11;存在 2-交錯(cuò)圈 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個(gè) 2-點(diǎn)不相鄰,從而 G2中也不含奇圈,所以 G2是森林.

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

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

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

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

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

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

驗(yàn)證新權(quán):

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

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

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

當(dāng) f是 4+-面時(shí),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)時(shí),根據(jù) R1,它的 2-master給它權(quán) 2,故 ch＊(v)=-2+2=0.

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

證明 對(duì) |V(G)|+|E(G)|用數(shù)學(xué)歸納法.當(dāng) |V(G)|+|E(G)|≤5時(shí),結(jié)論顯然成立.當(dāng) |V(G)|+|E(G)|≥6且Δ(G)≤6時(shí),只要令 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é)報(bào):自然科學(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é)任編輯 陶立方)