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

• 作 者: 石淼
• 机 构: 北京交通大学
• 出 处: 北京交通大学
• 发表日期: 2010年01期
• 关键词: 点荫度 2-退化图 3-退化图 k-退化图 Mycielski图

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