论文部分内容阅读
本文中所涉及的图均为有限简单图。图G的点荫度va(G)是由Chartrand,Kronk和Wall[1]最早提出来的,而且他们在文[1]中证明了平面图的点荫度va(G)≤3。在本文中,我们所要证明了k-退化图的M图的点荫度va(G)≤[(κ+1)/2],其中,2-退化图、3-退化图的点荫度va(G)=2。
图G的点荫度为图G的顶点集V(G)的最小划分数,其中每个点划分集的导出子图是一个森林,记为va(G)[8]。
若图G的任一子图H均含有一个度至多为κ的顶点,则称图G为k-退化图[8]。
由简单图G产生包含G的一个简单图G,从顶点集合为{v1… vn}的图G开始,添加顶点集U={u1…un}和一个另外的顶点ω,然后添加一些边使得ui与NG(vi)中的顶点都邻接,最后令N(ω)=U,称G为G的Mycielski图[26],简称M图。
在文[24]中,Garey和Johnson证明了导出森林的k-划1分(κ≥3)问题是NP-完全问题,故图G的点荫度也为NP-完全问题。对于点荫度问题,非平面图的点荫度的计算非常困难,所以目前主要研究的是平面图的点荫度。本文中,主要研究k-退化图的M图的点荫度,而大部分的k-退化图的M图为非平面图。
首先,我们在第一章中较为详细地介绍了图论的一些背景知识及相关概念。同时,我们对本文所要研究的k-退化图以及图的点荫度作了详细的介绍。
在第二章中,主要是介绍一些k-退化图已有的结论,借助于这些已有的结论对k-退化作更深入的了解。
第三章是本文最重要的一章,基于Andre Raspaud和Weifan Wang[8]证明的k-退化图的点荫度的结论va(G)≤[(κ+1)/2],本文得到了以下三个结论:
定理3.2.2若图G为2-退化图,H为G的M图,则va(H)=2;
定理3.2.3若图G为3-退化图,H为G的M图,则va(H)=2;
定理3.2.4若图G为k-退化图,H为G的M图,则va(H)≤[(κ+1)/2];并就此引申出来的两个结论作了初步的猜测与研究。