某些圖的線性蔭度問題

王雪梅

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

1 引 理

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

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

2 主要結(jié)果

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

(1)存在一個點(diǎn)u， 使得d(u)=7；

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

則有以下兩種情況：

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

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

證明(1) 若v′不是最大度點(diǎn)，則令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的鄰點(diǎn)v1必為最大度點(diǎn).

下面證明最大度點(diǎn)的唯一性.

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

與原假設(shè)矛盾.

與原假設(shè)矛盾.

以上矛盾說明:G只有一個最大度點(diǎn).

證畢.

3 結(jié) 論

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

參考文獻(xiàn)：

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

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

[3] 吳建良.Halin圖的一些路分解[J].山東礦業(yè)學(xué)院學(xué)報(bào)：自然科學(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.