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

来源 :北京交通大学 | 被引量 : 0次 | 上传用户:xiaogui999
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文中所涉及的图均为有限简单图。图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];并就此引申出来的两个结论作了初步的猜测与研究。
其他文献
本文给出了自由逆半群关于次数字典序的一个 Grobner-Shirshov 基和一组(唯一的且最短的)正规形.   全文共分四部分.前言简单地介绍了 Grobner-Shirshov 基理论和自由逆半群
本文用代数数论和p-adic分析的方法,求得椭圆曲线6Y2=X3-X+6上的全部整数点(x,y)=(1,±1),(0,±1),(6,±6),(9,±11),(23,±45),(25,±51),(64,±209),(13776,±660099)。同时给出了方程(x3)=8
本文主要研究Witt代数和W(2,2)代数上的模导子代数结构,进而确定了Witt代数和W(2,2)代数上的交换的Post-Lie代数结构(CPA结构)。第一章介绍了课题研究的主要意义及国内外发展前景
摘要:发光细菌是一种能够在正常条件下发出可见光的细菌,大都生活在海洋中。野生发光细菌和基因工程发光细菌应用于环境检测,大大提高了环境检测的准确性、灵敏性。本文综述了发光真菌分类、发光机制以及发光真菌在环境检测中的应用,对发光真菌生物传感器的研究发展情况进行了简要分析,以供参考。  关键词:发光细菌 环境检测 研究  一、发光真菌分类  发光真菌,尤其是海洋真菌发光,是一种很早就被人们知晓的生物现象
期刊