图的线性2-荫度

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:littleycy
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图G的线性k-荫度lak(G)是指最小的正整数m,使得G的边集能被剖分成m个边不交的集合,满足每一个集合是森林,且森林中每一个连通分支都是长度至多为k的路.当取到两个极端情况时,la1(G)显然为图G的边色数;la∞(G)则为图G的线性荫度la(G).1970年,Harary提出了图的线性荫度这个概念.而后在1980年,Akiyama,Exoo和Harary猜想,对于任何正则图G,有la(G)=「(△(G)+1)/2(]).因为对于任何图都有la(G)≥「△(G)/2(]),所以这个猜想等价于著名的线性荫度猜想(LAC):对任何简单图G,有「△(G)/2(])≤la(G)≤「(△(G)+1)/2(]).在这个猜想的推动下,Habib和Péroche(1982)进一步提出了线性k-荫度的概念,并给出一个关于线性k-荫度的猜想:若G是含有n个顶点的图,且k≥2是一个正整数,则lak(G)≤{「n△(G)+1/2([)kn/k+1」(])若△(G)≠n-1;「n△(G)/2([)kn/k+1」(])若△(G)=n-1.  本学位论文主要围绕图的线性2-荫度问题展开,探讨了平面图的线性2-荫度,环面图的线性2-荫度以及稀疏图的线性2-荫度问题,分为以下五个部分:  第一章介绍了本文用到的定义,符号及专业术语,简述了相关领域的研究现状并呈现了本文的主要研究结果.同时,给出了线性2-荫度的几个性质引理.  第二章将证明两个边剖分定理,这在后面几章中证明我们的主要结论至关重要  第三章考虑环面图G的线性2-荫度问题,证明了:(1)la2(G)≤「△(G)+1/2(])+7;(2)若G不含某个k-圈,其中k∈{3,4,5},则la2(G)≤「△(G)+1/2(])+4.  在第四章中研究2-退化图,最大平均度较小时的稀疏图的线性2-荫度.证明了:(1)若G为2-退化图,则la2(G)≤「△(G)/2(])+2;(2)若mad(G)<4,则la2(G)≤「△(G)+1/2(])+4;(3)若mad(G)<7/2,则la2(G)≤「△(g)+1/2(])+3;(4)若mad(G)<5,则la2(G)≤「△(G)+1/2(])+10.  第五章研究最大度较大时的平面图的线性2-荫度问题.证明了若G是△(G)≥9的平面图,则la2(G)≤△(G)-1.
其他文献
脑电波是大脑皮层神经元的电生理活动而产生的信号,它包含了人体大量的信息。其中,睡眠脑电波则体现了人在睡眠阶段下脑电的变化。人一生中大约1/3的时间处于睡眠阶段,故睡眠
半群的代数理论是一门崭新的学科.近年来随着计算机科学的发展以及该学科在各领域的应用,使得这门学科在数学及科学发展中的地位日益突出.本文主要对半群的代数理论的一类主要
K(a)hler流形中的哈密顿极小拉格朗日子流形是指在哈密顿形变下,拉格朗日子流形的体积泛函极小。最早由Oh在1990年提出来,类似概念的是Harvey和Lawson的特殊拉格朗日子流形,实际
基于拓扑度理论和不动点定理,本文研究了几类泛函微分差分方程的周期解的存在性问题。全文包括五章。   第一章简要介绍了泛函微分方程的发展和本文的主要研究工作。  
本论文研究了自治和非自治强阻尼随机波动方程随机吸引子的存在性及其分形维数上界.本论文主要分为三章:  第一章,首先介绍研究问题的背景与研究现状.然后介绍随机动力系统
本文主要研究了两方面的内容:基于公钥的概率密码体制和BG概率密码体制的一个改进方案。  在基于RSA的概率密码体制部分,文章分析了公钥密码体制可以实现数字签名,但是公钥密