论文部分内容阅读
本论文研究了图的线性荫度和点荫度问题,文中所涉及的图均为有限简单图。 图G的点荫度va(G)是由Chartrand,Kronk和Wallt最早提出来的。 图G的线性荫度的概念最早是由Harary在[12]中提出来的.用la(G)和△(G)分别表示图的线性荫度和最大度.在线性荫度的研究中有一个非常著名的线性荫度猜想:对任何的简单图G,有[△(G)/2]≤la(G)≤[△(G)+1/2] 在第一章中,我们较为详细地介绍了本文的一些背景知识,所用到的基本概念以及主要结论。 在第二章中,我们首先给出了三次方图的定义:任意两点u,v∈V(G),它们之间的距离指的是这两点之间的最短路的长度,我们用dG(u,v)来表示.在图G的三次方图G3中,V(G3)=V(G),E(G3)={uv:u,v∈V(G),u≠v,dG(u,v)≤3}.接着讨论了当图G的最大度为△时,其三次方图G3的点荫度满足[△+1/2]≤va(G3)≤[△3-△2+△+1/2]。最后对圈Gn的三次方图Cn3的点荫度进行了研究。 在第三章中,我们考虑了平面图的线性荫度问题,讨论了不含3-圈的平面图的结构特点,并且证明了△(G)=7且不含3-圈的平面图满足线性荫度猜想。