王雪梅,李會序
(河南工程學院 數(shù)理科學系, 河南 鄭州 451191)
先介紹一些定義:
設M(e)=max{dG(x),dG(y)},M*(G)=min{M(e)|e∈E(G)},對于圖G的一個面f,設ni(f)為f的邊界b(f)上的i-點數(shù),對于s≥2,偶圈C=v1v2…v2sv1稱為一個(2,k)-交錯圈,若dG(v1)=dG(v3)=…=dG(v2s-1)=2且dG(v2)=dG(v3)=…=dG(v2s)=k.
引理3 對于圖G,有l(wèi)a2(G)≤Δ(G).
下面給出2個主要定理的證明.
定理1 若G為一個連通且無割邊的平面圖,Δ(G)≥2,且不含3-圈和4-圈,則或者M*(G)≤5或者存在一個(2,6)-交錯圈.
證明假設G為一個反例.即G是一個連通的平面圖,不含3-圈和4-圈,不含(2,6)-交錯圈,Δ(G)≥2,且對于任何,一條邊e,都有M(e)≥6,有以下斷言成立:
斷言2 對每個頂點v∈V(G),都有n2(v)+n3(v)≤dG(v).
設ω為定義在V(G)∪F(G)上的權(quán)函數(shù).若v∈V(G),則設ω(v)=dG(v)-4.
若f∈F(G),則設ω(f)=dG(f)-4,所以由歐拉公式得:
設新規(guī)則為:
先考慮f∈F(G):
若dG(f)≥8,由斷言1得
接下來考慮點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個度大于等于6的點相鄰,又因為圖中無割邊,則v至少與3個面關(guān)聯(lián),則
定理1證明完畢.
定理2 設G是一個無割邊的連通圖,若M*(G)≤5或G含有一個(2,6)-交錯圈,則G可分解為一個森林T和一個子圖H,使得Δ(T)≤max{2,Δ(G)-4},Δ(H)≤4.
證明對G的邊數(shù)|E(G)|進行歸納.當|E(G)|≤1時,結(jié)論顯然成立.
設G為一個|E(G)|≥2的連通圖.
若M*(G)≤5,從|E(G)|中選擇一條邊xy,使得dG(x),dG(y)≤5.設G′=G-xy.由歸納假設,可以構(gòu)造出G′的一個邊分解T′∪H′,且Δ(T′)≤max{2,Δ(G′)-4},Δ(H′)≤4,使得x,y至少與T′的一條邊關(guān)聯(lián). 此時dH′(x)≤dG(x)-2≤3,dH′(y)≤dG(y)-2≤3,令T=T′,H=H′∪{xy},從而G=H∪T即是所要求的邊分解. 此種情況得證.
若存在一個(2,6)-交錯圈,C=x1y1x2y2…xnynx1,使得dG(xi)=2,且dG(yi)=6,n≥2,i=1,2…n.設G′=G-E(C),假設G′可以邊分解為T′∪H′,使得Δ(T′)≤max{2,Δ(G′)-4},Δ(H′)≤4. 假設每個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}.因為dT(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可分解為一個森林T和一個子圖H,使得Δ(T)≤max{2,Δ(G)-4},Δ(H)≤4.
推論2 每個不含3-圈和4-圈且Δ(G)≥6的平面圖G都可分解為一個森林T和一個子圖H,使得Δ(T)≤Δ(G)-4,Δ(H)≤4.
證明G可以邊分解為一個森林T和一個子圖H,使得Δ(T)≤max{2,Δ(G)-4},Δ(H)≤4.
若Δ(G)≥6,則由推論2,G可以邊分解為一個森林T和一個子圖H,使Δ(T)≤Δ(G)≤-4,Δ(H)≤4,從而
參考文獻:
[1] 邦迪J A,默蒂U S R.圖論及其應用[M].北京:科學出版社,1984.
[2] 吳建良.邊數(shù)較少的圖的線性蔭度[J].山東大學學報:理學版,2005,40 (3):11-14.
[3] 吳建良.Halin圖的一些路分解[J].山東礦業(yè)學院學報:自然科學版,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.