关于特殊图的彩虹连通数的研究

发布时间：2017-11-07 20:41

  本文关键词：关于特殊图的彩虹连通数的研究

  更多相关文章： 特殊图 彩虹连通数 彩虹顶点连通数

【摘要】：著名的格尼斯堡七桥问题是图论问题的起源,随后图论便成为应用数学研究中的一个重要分支。特殊图的染色问题一直是图论研究领域的热门问题,它不但具有理论价值,更具有重要的现实意义。连通性是图论中最重要的性质之一,基于这些方面,一种加强版的连通性概念——图的彩虹连通性的问题应运而生。在2008年,Chartrand、Johnson等人最先把这个概念引入到文献中。在过去的几年里,图的彩虹连通数一直作为图论中的热门问题受到众多数学专家的广泛关注,同时也被应用到网络信息安全、密码学等领域。如果G是一个非平凡连通图,对G的边全部染上颜色。若用数字表示颜色,则c:E(G)→ {1,2,…,kk∈N}即G为的一种着色方式。当经过图G中的一条路P上的边都被染成不同颜色时,则称路P为图G的一条彩虹路。如果对于连通图G来说,任意两点间都存在一条彩虹路,则称图G是彩虹连通的。称使得图G为彩虹路连通的所使用的最少颜色数k为图G的彩虹连通数,记为rc(G)。其后,Krivelevich和Yuster提出了彩虹顶点连通的概念。显然这是对图形的顶点进行染色。一个连通图的任意两个顶点之间至少存在一条内部顶点染成不同颜色的路相连,则称该图是彩虹顶点连通的。类比图的彩虹连通数的概念可知,彩虹顶点连通数就是使得连通图G彩虹顶点连通的所必须的起码的颜色数,记为rvc(G)。本文研究了一些特殊图的彩虹连通性的问题,主要结果如下：(1)介绍了彩虹连通性问题的基本概念和已有的结论。(2)利用数学归纳法、分类讨论思想,计算出了完全图刺图、圈的刺图、风车图的彩虹连通数及强彩虹连通数。(3)运用数学归纳法和分类讨论的的数学思想,将原有图进行推广,对一些日晕图的彩虹连通数问题进行了研究。(4)对3-连通图的彩虹顶点连通数进行了求解。
【学位授予单位】：大连海事大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】

中国博士学位论文全文数据库 前3条

1 陈莉莉;关于图的彩虹（顶点）连通数若干问题的研究[D];南开大学;2014年

2 李恒哲;图的彩虹连通数与距离[D];南开大学;2013年

3 董九英;图的彩虹连通数的若干上界[D];南开大学;2013年

中国硕士学位论文全文数据库 前1条

1 刘怡筱;关于特殊图的彩虹连通数的研究[D];大连海事大学;2016年

，

本文编号：1154048