不含3-圈和4-圈的平面圖的線性2-蔭度

王雪梅,李會(huì)序

(河南工程學(xué)院 數(shù)理科學(xué)系， 河南 鄭州 451191)

先介紹一些定義:

設(shè)M(e)=max{dG(x),dG(y)},M*(G)=min{M(e)|e∈E(G)},對(duì)于圖G的一個(gè)面f,設(shè)ni(f)為f的邊界b(f)上的i-點(diǎn)數(shù),對(duì)于s≥2,偶圈C=v1v2…v2sv1稱為一個(gè)(2,k)-交錯(cuò)圈,若dG(v1)=dG(v3)=…=dG(v2s-1)=2且dG(v2)=dG(v3)=…=dG(v2s)=k.

引理3 對(duì)于圖G,有l(wèi)a2(G)≤Δ(G).

1 結(jié)論

下面給出2個(gè)主要定理的證明.

定理1 若G為一個(gè)連通且無(wú)割邊的平面圖,Δ(G)≥2,且不含3-圈和4-圈,則或者M(jìn)*(G)≤5或者存在一個(gè)(2,6)-交錯(cuò)圈.

證明假設(shè)G為一個(gè)反例.即G是一個(gè)連通的平面圖,不含3-圈和4-圈,不含(2,6)-交錯(cuò)圈,Δ(G)≥2,且對(duì)于任何,一條邊e,都有M(e)≥6,有以下斷言成立:

斷言2 對(duì)每個(gè)頂點(diǎn)v∈V(G),都有n2(v)+n3(v)≤dG(v).

設(shè)ω為定義在V(G)∪F(G)上的權(quán)函數(shù).若v∈V(G),則設(shè)ω(v)=dG(v)-4.

若f∈F(G),則設(shè)ω(f)=dG(f)-4,所以由歐拉公式得:

設(shè)新規(guī)則為:

先考慮f∈F(G):

若dG(f)≥8,由斷言1得

接下來(lái)考慮點(diǎn)v∈V(G),由于Δ(G)≥2,因此,dG(v)≥2.

若dG(v)=4, 則ω′(v)=ω(v)=0;

若dG(v)=5, 則ω′(v)=ω(v)=5-4=1>0;

若dG(v)≥6, 則由斷言2得

若dG(v)=2,則v與2個(gè)度大于等于6的點(diǎn)相鄰,又因?yàn)閳D中無(wú)割邊,則v至少與3個(gè)面關(guān)聯(lián),則

定理1證明完畢.

定理2 設(shè)G是一個(gè)無(wú)割邊的連通圖,若M*(G)≤5或G含有一個(gè)(2,6)-交錯(cuò)圈,則G可分解為一個(gè)森林T和一個(gè)子圖H,使得Δ(T)≤max{2,Δ(G)-4},Δ(H)≤4.

證明對(duì)G的邊數(shù)|E(G)|進(jìn)行歸納.當(dāng)|E(G)|≤1時(shí),結(jié)論顯然成立.

設(shè)G為一個(gè)|E(G)|≥2的連通圖.

若M*(G)≤5,從|E(G)|中選擇一條邊xy,使得dG(x),dG(y)≤5.設(shè)G′=G-xy.由歸納假設(shè),可以構(gòu)造出G′的一個(gè)邊分解T′∪H′,且Δ(T′)≤max{2,Δ(G′)-4},Δ(H′)≤4,使得x,y至少與T′的一條邊關(guān)聯(lián). 此時(shí)dH′(x)≤dG(x)-2≤3,dH′(y)≤dG(y)-2≤3，令T=T′,H=H′∪{xy}，從而G=H∪T即是所要求的邊分解. 此種情況得證.

若存在一個(gè)(2,6)-交錯(cuò)圈,C=x1y1x2y2…xnynx1,使得dG(xi)=2，且dG(yi)=6,n≥2,i=1,2…n.設(shè)G′=G-E(C),假設(shè)G′可以邊分解為T′∪H′,使得Δ(T′)≤max{2,Δ(G′)-4},Δ(H′)≤4. 假設(shè)每個(gè)yi都與T′中至少一條邊關(guān)聯(lián),則dH′(yi)≤dG(yi)-3=6-3=3,i=1,2…,n.令T=T′∪{x1y1,x2y2,…xnyn},H=H′∪{y1x2,y2x3,…ynx1}.因?yàn)閐T(xi)=1,T為森林,而且dH(xi)=1且dH(yi)≤dH′(yi)+1≤4.dH(t)=dH′(t)≤4t∈V(H)/V(C).從而H∪T為G的滿足要求的邊分解.

推論1 若G是不含3-圈和4-圈的平面圖,Δ(G)≥2,則G可分解為一個(gè)森林T和一個(gè)子圖H,使得Δ(T)≤max{2,Δ(G)-4},Δ(H)≤4.

推論2 每個(gè)不含3-圈和4-圈且Δ(G)≥6的平面圖G都可分解為一個(gè)森林T和一個(gè)子圖H,使得Δ(T)≤Δ(G)-4,Δ(H)≤4.

證明G可以邊分解為一個(gè)森林T和一個(gè)子圖H,使得Δ(T)≤max{2,Δ(G)-4},Δ(H)≤4.

若Δ(G)≥6,則由推論2,G可以邊分解為一個(gè)森林T和一個(gè)子圖H,使Δ(T)≤Δ(G)≤-4,Δ(H)≤4,從而

參考文獻(xiàn)：

[1] 邦迪J A,默蒂U S R.圖論及其應(yīng)用[M].北京:科學(xué)出版社，1984.

[2] 吳建良.邊數(shù)較少的圖的線性蔭度[J].山東大學(xué)學(xué)報(bào):理學(xué)版,2005,40 (3):11-14.

[3] 吳建良.Halin圖的一些路分解[J].山東礦業(yè)學(xué)院學(xué)報(bào):自然科學(xué)版,1996(15):219-222.

[4] Habib M P.Some problems about linear arboricity[J].Discrete Math,1982,41(2):219-220.

[5] Bermond J C,Fouquet J L, Habib M,et a1.On linear k-arboricity[J]. Discrete Math,1984,52(2/3):123-132.

[6] Jackson B, Wormald N C. On the linear k-arboricity of cubic graphs[J]．Discrete Math,1996，162(1/3):293-297.

[7] Aldred R E L, Wormald N C. More on the linear k-arboricity of regular graphs[J]．Australas J Combin,1998,18(1):104-197.

[8] Chen Bailiang, Fu Henglin, Huang Guoqing． Decomposing graphs into forests of paths with size less than three[J].Australas J Combin,1991,3(1):155-173．

[9] Fu Henglin, Huang Guoqing. The linear 2-arboricity of complete bipartite graphs[J]．Ars Combin,1994,38(3):309-318.

[10] 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 Combin Theory Ser B,1999,75(1):100-109．

[11] Zhang Zhenhua. Algorithmic aspects of linear k-arboricity[J]．Taiwanese J Math,1999,3(1):73-81.

[12] Zhang Zhenhua, Chen Bailiang, Fu Henglin, et al. Linear k-arboricities on trees[J]．Discrete Appl Math,2000,103 (1/3):281-287.

[13] Akiyama J.Three Developing Topics in Graph Theory[D]. Tokyo: University of Tokyo，1980.

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

[15] Akiyama J,Exoo G,Harary F.Covering and packing in graphs III:cyclic and acyclic invariants[J].Math Slovaca,1980(30):405-406.