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

        ?

        某些圖的線性蔭度問題

        2010-11-27 01:45:40王雪梅
        關(guān)鍵詞:矛盾

        王雪梅

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

        1 引 理

        下面是兩個本文將用到的引理.

        引理1[2-8]若一個連通圖G滿足Δ=1,2,3,4,5,6,8,則LAC成立.

        2 主要結(jié)果

        下面給出本文所給的結(jié)果.

        (1)存在一個點u, 使得d(u)=7;

        (3)任意兩個最大度點都不相鄰.

        則有以下兩種情況:

        (2)若G是第二類的圖,則必是最小的第二類圖,且有以下兩個結(jié)論成立:

        ②若G有度數(shù)為1的頂點v0, 則它只有唯一的最大度點.這個最大度點就是與v0相鄰的頂點.

        證明(1) 若v′不是最大度點,則令G′=G-u′v′, 有e(G′)=e(G)-1,v(G′)=v(G),

        Δ+1, 所以dG′(u′)+dG(v′)≤Δ-2,

        dG′(u′)+dG′(v′).

        與原假設(shè)矛盾, 所以結(jié)論1成立.

        從而由結(jié)論1知,v0的鄰點v1必為最大度點.

        下面證明最大度點的唯一性.

        t≤2. 這就是說t=2.

        與原假設(shè)矛盾.

        與原假設(shè)矛盾.

        以上矛盾說明:G只有一個最大度點.

        證畢.

        3 結(jié) 論

        圖論中有關(guān)染色的研究成果已經(jīng)相對完善,對網(wǎng)絡(luò)方面和運輸問題的作用也日趨明顯[9-15].但是染色理論分支的蔭度問題還有一些尚待解決,本文找出了第一類圖和第二類圖的一個必要條件,但是它的充分條件問題還有待解決.

        參考文獻(xiàn):

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

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

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

        [4] WU J L. The linear arboricity of Series-Parallel graphs[J]. Graphs and Comb,2000(16):367-372.

        [5] WU J L. On the linear arboricity of planar graphs[J]. J Graph Theory, 1999(31):129-134.

        [6] ALON N. The linear arboricity of graphs[J]. Mathematics, 1988(62): 311-325.

        [7] ENOMOTO H, PEROCHE B.The linear arboricity of some regular graphs[J]. J Graph Theory,1984(8):309-324.

        [8] GULDAN F. Some results on linear arboricity[J]. Graph Theory, 10 (1986): 505-509.

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

        [10]BERMOND J C,F(xiàn)OUQUET J L, HABIB M,et a1.On linear k-arboricity[J]. Discrete Math,1984,52(2/3):123-132.

        [11]FU H G, HUANG G Q. The linear 2-arboricity of complete bipartite graphs[J].Ars Combin,1994,38(3):309-318.

        [12]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.

        [13]ZHANG Z H. Algorithmic aspects of linear k-arboricity[J].Taiwanese J Math,1999,3(1):73-81.

        [14]ZHANG Z H. CHEN B L, FU H L, et a1. Linear k-arboricities on trees[J].Discrete Appl Math, 2000,103 (1/3):281-287.

        [15]AKIYAMA J.Three developing topics in graph theory[D]. Tokyo: University of Tokyo,1980.

        猜你喜歡
        矛盾
        咯咯雞和嘎嘎鴨的矛盾
        幾類樹的無矛盾點連通數(shù)
        對待矛盾少打“馬賽克”
        再婚后出現(xiàn)矛盾,我該怎么辦?
        中老年保健(2021年2期)2021-08-22 07:29:58
        矛盾心情的描寫
        矛盾的我
        對矛盾說不
        童話世界(2020年13期)2020-06-15 11:54:50
        愛的矛盾 外一首
        實現(xiàn)鄉(xiāng)村善治要處理好兩對矛盾
        這個圈有一種矛盾的氣場
        商周刊(2017年11期)2017-06-13 07:32:30
        理论片午午伦夜理片影院| 99久久精品人妻少妇一| 成人影院在线视频免费观看| 亚洲中文字幕成人无码| 亚洲熟妇色xxxxx欧美老妇y| 国产日韩欧美视频成人| 青青草视频免费在线播放| www国产亚洲精品| 越猛烈欧美xx00动态图| 日本a在线免费观看| 中文字幕专区一区二区| 中文字幕亚洲乱码成熟女1区| 日韩欧群交p片内射中文| 国产 中文 制服丝袜 另类| 国产激情免费观看视频| 人人妻人人澡人人爽精品日本| 欧美黑人xxxx又粗又长| 国产在线网址| 国产视频一区二区三区在线看| 手机在线亚洲精品网站| 国产suv精品一区二区6| 免费看欧美日韩一区二区三区| 国产91在线精品观看| 欧洲熟妇色xxxx欧美老妇软件| 全免费a级毛片| 亚洲有码转帖| 尤物AV无码色AV无码麻豆| 国产成人av三级在线观看韩国| 高潮内射双龙视频| 7878成人国产在线观看| 少妇特殊按摩高潮不断| 国产一区亚洲二区三区| 亚洲国产精品日韩av专区| 亚洲福利天堂网福利在线观看| 97成人精品在线视频| 欧美变态另类刺激| 久青草国产视频| 久久精品国产精品亚洲婷婷| 激情综合婷婷色五月蜜桃| 国产大学生粉嫩无套流白浆 | 青青草视频在线观看网|