亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

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

        2011-11-24 06:57:52王雪梅李會序

        王雪梅,李會序

        (河南工程學院 數(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).

        1 結(jié)論

        下面給出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.

        无码超乳爆乳中文字幕| 伊人久久大香线蕉av色| 久久久亚洲成年中文字幕| 国产极品美女高潮无套| 人妻激情另类乱人伦人妻| 亚洲欧美日韩综合在线观看| 日本最新一区二区三区视频| 国产午夜亚洲精品国产成人av| 特级毛片a级毛片100免费播放| 国产av天堂成人网| 白色橄榄树在线阅读免费| 伊人久久这里只有精品| 一品二品三品中文字幕| 91白浆在线视频| 久久精品国产亚洲av日韩精品| 欧美群妇大交群| 使劲快高潮了国语对白在线| a级国产精品片在线观看| 日韩不卡一区二区三区色图| 中文字幕色av一区二区三区| 天天影视色香欲综合久久| 亚洲国产一区二区三区,| h视频在线播放观看视频| 极品av麻豆国产在线观看| 国产免费一区二区三区最新不卡| 久久久人妻丰满熟妇av蜜臀| 黑人大群体交免费视频| 人妻少妇av无码一区二区| 精品久久久久久国产潘金莲| 亚洲精品偷拍自综合网| 窝窝午夜看片| 久久久久欧洲AV成人无码国产| 国产精品天堂在线观看| 极品尤物一区二区三区| 欧美日韩不卡视频合集| 青青青伊人色综合久久| 熟女人妻中文字幕av| 中文字幕亚洲情99在线| av无码特黄一级| 亚洲av日韩一卡二卡| 亚洲产国偷v产偷v自拍色戒|