k-退化图的M图的点荫度

摘要

本文中所涉及的图均为有限简单图。图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]；并就此引申出来的两个结论作了初步的猜测与研究。

目录

文摘

英文文摘

致谢

第一章 绪论

1.1 背景知识

1.2 基本概念

1.3 k-退化图

1.3.1 k-退化图的背景知识

1.3.2 k-退化图已有的结论

1.4 图的点荫度

1.4.1 点荫度的背景知识

1.4.2 点荫度已有的结论

第二章 k-退化图及M图的相关结论

2.1 k-退化图的相关结论

2.1.1 k-退化图的游戏荫度

2.1.2 k-退化图的游戏色指数

2.1.3 k-退化图的重着色

2.2 M图的相关结论

2.2.1 M图的全色数

2.2.2 M图的边色数

第三章 K-degenerate图的M-图的点荫度

3.1 预备知识

3.2 主要结论

3.3 总结与展望

参考文献

学位论文数据集