论文部分内容阅读
图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.