一些特殊图类的线性荫度和线性2-荫度

发布时间：2020-08-17 12:19

【摘要】：线性森林是所有的连通分支都是路的图,而线性k-森林是所有的连通分支都是长度不超过k的路的图.1970年,Harary提出了图的线性荫度的概念,图的线性荫度就是把图的边集分解成互不相交的线性森林的最少数目,用符号la(G)表示.1980年,Akiyama,Exoo和Harary提出了如下猜想:对任意r-正则图G,有la(G)=「r+1/2」.这亦即著名的LAC猜想:对任意简单图G,有「△(G)/2」≤la(G)≤「△(G)+1/2」.1982年,Habib和Peroche进一步提出了图的线性kk-荫度的概念,图的线性kk-荫度就是把图的边集分解成互不相交的线性kk-森林的最少数目,用符号lak(G)表示.他们猜想:对n个点的图G(kk ≥ 2),有特别地,当k = 2时,就是线性2-荫度,用符号la2(G)表示.本文主要研究一些特殊图类的线性荫度和线性2-荫度,同时,对现有的一些结论进行了重新证明.下面是本文的结构:第一章,我们主要先介绍了本文需要用到的一些基本概念与符号,接着,介绍相关问题的历史背景以及发展现状,最后,阐述了本文的主要结论.第二章,我们主要研究了图的线性荫度,给出了伪树的线性荫度.受九龙树猜想证明的启发,重新证明了 3-正则图和4-正则图的线性荫度.第三章,我们主要研究了图的线性2-荫度.首先,通过找一个合适的(t,2)-线性染色给出了伪树的线性2-荫度;接下来,利用权分配的方法研究了一些特殊平面图的结构性质,定义了(k,1)-图;最后,给出了(k,1)-图以及一些特殊平面图的线性2-荫度的结论.第四章,我们主要阐述了未来需要进一步研究的问题.
【学位授予单位】：福州大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 左连翠;吴建良;刘家壮;;整数距离图G(D_(m，k，2))的点线性荫度[J];系统科学与数学;2006年05期

2 罗朝阳;孙林;;6-圈至多含一弦平面图的线性荫度[J];运筹学学报;2019年02期

3 范勤亮;;三正则图的列表线性荫度(英文)[J];新疆大学学报(自然科学版);2009年03期

4 左连翠;刘金国;李臣顺;;整数距离图G(D_(m,3))的点线性荫度[J];山东大学学报(工学版);2006年01期

5 左连翠,李涛,李霞;整数距离图G(D_(m,2))的点线性荫度[J];山东大学学报(理学版);2004年06期

6 吴建良;Halin图的一些路分解[J];山东矿业学院学报;1998年01期

7 吕长青;;上可嵌入图与次上可嵌入图的线性荫度[J];华东师范大学学报(自然科学版);2015年01期

8 王雪梅;;某些图的线性荫度问题[J];河南工程学院学报(自然科学版);2010年04期

9 陶f 昀;林文松;;笛卡尔积图的线性荫度(英文)[J];Journal of Southeast University(English Edition);2013年02期

10 吴建良;边数较少的图的线性荫度[J];山东大学学报(理学版);2005年03期

相关博士学位论文 前4条

1 许仁誉;平面图的列表点（边、全）染色和列表线性荫度[D];山东大学;2017年

2 谭香;平面图的线性荫度、均匀染色和全染色[D];山东大学;2011年

3 安新慧;图中的哈密顿圈和图的列表线性荫度[D];新疆大学;2008年

4 王慧娟;可嵌入图的染色问题[D];山东大学;2014年

相关硕士学位论文 前7条

1 郭建民;一些特殊图类的线性荫度和线性2-荫度[D];福州大学;2018年

2 金政国;平方图的点荫度[D];北京交通大学;2010年

3 邵正波;Local Cut Lemma在有向图的线性印度和K_γ图的无圈染色中的应用[D];河南大学;2017年

4 范勤亮;三正则图的列表线性荫度及线性点可选性[D];新疆大学;2009年

5 薛兵;图的线性荫度和线性k-荫度[D];天津师范大学;2010年

6 马刚;平方图的点荫度[D];山东大学;2007年

7 吴玉文;关于可平面图的边剖分的若干结果[D];山东大学;2007年

本文编号：2795315