【摘要】：線性森林是所有的連通分支都是路的圖,而線性k-森林是所有的連通分支都是長(zhǎng)度不超過(guò)k的路的圖.1970年,Harary提出了圖的線性蔭度的概念,圖的線性蔭度就是把圖的邊集分解成互不相交的線性森林的最少數(shù)目,用符號(hào)la(G)表示.1980年,Akiyama,Exoo和Harary提出了如下猜想:對(duì)任意r-正則圖G,有l(wèi)a(G)=「r+1/2」.這亦即著名的LAC猜想:對(duì)任意簡(jiǎn)單圖G,有「△(G)/2」≤la(G)≤「△(G)+1/2」.1982年,Habib和Peroche進(jìn)一步提出了圖的線性kk-蔭度的概念,圖的線性kk-蔭度就是把圖的邊集分解成互不相交的線性kk-森林的最少數(shù)目,用符號(hào)lak(G)表示.他們猜想:對(duì)n個(gè)點(diǎn)的圖G(kk ≥ 2),有特別地,當(dāng)k = 2時(shí),就是線性2-蔭度,用符號(hào)la2(G)表示.本文主要研究一些特殊圖類(lèi)的線性蔭度和線性2-蔭度,同時(shí),對(duì)現(xiàn)有的一些結(jié)論進(jìn)行了重新證明.下面是本文的結(jié)構(gòu):第一章,我們主要先介紹了本文需要用到的一些基本概念與符號(hào),接著,介紹相關(guān)問(wèn)題的歷史背景以及發(fā)展現(xiàn)狀,最后,闡述了本文的主要結(jié)論.第二章,我們主要研究了圖的線性蔭度,給出了偽樹(shù)的線性蔭度.受九龍樹(shù)猜想證明的啟發(fā),重新證明了 3-正則圖和4-正則圖的線性蔭度.第三章,我們主要研究了圖的線性2-蔭度.首先,通過(guò)找一個(gè)合適的(t,2)-線性染色給出了偽樹(shù)的線性2-蔭度;接下來(lái),利用權(quán)分配的方法研究了一些特殊平面圖的結(jié)構(gòu)性質(zhì),定義了(k,1)-圖;最后,給出了(k,1)-圖以及一些特殊平面圖的線性2-蔭度的結(jié)論.第四章,我們主要闡述了未來(lái)需要進(jìn)一步研究的問(wèn)題.
【學(xué)位授予單位】：福州大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類(lèi)號(hào)】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 左連翠;吳建良;劉家壯;;整數(shù)距離圖G(D_(m，k，2))的點(diǎn)線性蔭度[J];系統(tǒng)科學(xué)與數(shù)學(xué);2006年05期

2 羅朝陽(yáng);孫林;;6-圈至多含一弦平面圖的線性蔭度[J];運(yùn)籌學(xué)學(xué)報(bào);2019年02期

3 范勤亮;;三正則圖的列表線性蔭度(英文)[J];新疆大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年03期

4 左連翠;劉金國(guó);李臣順;;整數(shù)距離圖G(D_(m,3))的點(diǎn)線性蔭度[J];山東大學(xué)學(xué)報(bào)(工學(xué)版);2006年01期

5 左連翠,李濤,李霞;整數(shù)距離圖G(D_(m,2))的點(diǎn)線性蔭度[J];山東大學(xué)學(xué)報(bào)(理學(xué)版);2004年06期

6 吳建良;Halin圖的一些路分解[J];山東礦業(yè)學(xué)院學(xué)報(bào);1998年01期

7 呂長(zhǎng)青;;上可嵌入圖與次上可嵌入圖的線性蔭度[J];華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2015年01期

8 王雪梅;;某些圖的線性蔭度問(wèn)題[J];河南工程學(xué)院學(xué)報(bào)(自然科學(xué)版);2010年04期

9 陶f(shuō) 昀;林文松;;笛卡爾積圖的線性蔭度(英文)[J];Journal of Southeast University(English Edition);2013年02期

10 吳建良;邊數(shù)較少的圖的線性蔭度[J];山東大學(xué)學(xué)報(bào)(理學(xué)版);2005年03期

相關(guān)博士學(xué)位論文 前4條

1 許仁譽(yù);平面圖的列表點(diǎn)（邊、全）染色和列表線性蔭度[D];山東大學(xué);2017年

2 譚香;平面圖的線性蔭度、均勻染色和全染色[D];山東大學(xué);2011年

3 安新慧;圖中的哈密頓圈和圖的列表線性蔭度[D];新疆大學(xué);2008年

4 王慧娟;可嵌入圖的染色問(wèn)題[D];山東大學(xué);2014年

相關(guān)碩士學(xué)位論文 前7條

1 郭建民;一些特殊圖類(lèi)的線性蔭度和線性2-蔭度[D];福州大學(xué);2018年

2 金政國(guó);平方圖的點(diǎn)蔭度[D];北京交通大學(xué);2010年

3 邵正波;Local Cut Lemma在有向圖的線性印度和K_γ圖的無(wú)圈染色中的應(yīng)用[D];河南大學(xué);2017年

4 范勤亮;三正則圖的列表線性蔭度及線性點(diǎn)可選性[D];新疆大學(xué);2009年

5 薛兵;圖的線性蔭度和線性k-蔭度[D];天津師范大學(xué);2010年

6 馬剛;平方圖的點(diǎn)蔭度[D];山東大學(xué);2007年

7 吳玉文;關(guān)于可平面圖的邊剖分的若干結(jié)果[D];山東大學(xué);2007年

本文編號(hào)：2795315