图的线性荫度和点荫度

摘要

本论文研究了图的线性荫度和点荫度问题，文中所涉及的图均为有限简单图。
　　图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-圈的平面图满足线性荫度猜想。