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

《关于特殊图的彩虹连通数的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC密级单位代码!Q151大连海事大学硕士学位论文关于特殊图的彩虹连通数的研究刘怡筱指导教帅王．芯平职称教授学位授予单位大连海事大学申请学位类别理学硕士学科(专业)数学论文完成口期2015年12月答辩日期2016年3月答辩委员会’卜席万方数据TheRainbowconnectionofthespecialgraphAthesisSubmittedtoDalianMaritimeUniversityIIlllIlllIllllIIlY2999096InpartialfulfillmentoftherequirementsforthedegreeofMas

2、terofSciencebyLiuYixiao(AppliedMathematics)ThesisSupervisor：ProfessorWangZhipingMarch2016万方数据大连海事大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果，撰写成博／硕士学位论文：：苤王挂鐾图的受堑连通数的盟塞：：。除论文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体己经公开发表或未公开发表的成果。本声明的法律责任由本人承担。学位论

3、文作者签名：烈性救学位论文版权使用授权书本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。同意将本学位论文收录到《中国优秀博硕士学位论文全文数据库》(中国学术期刊(光盘版)电子杂志社)、《中国学位论文全文数据库》(中国科学技术信息研究所)等数据库中，并以电子出版物形式出版发行和提供信息服务。保密的论文在解密后遵守此

4、规定。本学位论文属于：保密口在年解密后适用本授权书。不保密口(请在以上方框内打“4”)论文作者签名：刘胳慑导师签名：日期：汐形年弓月，9日万方数据中文摘要摘要著名的格尼斯堡七桥问题是图论问题的起源，随后图论便成为应用数学研究中的一个重要分支。特殊图的染色问题一直是图论研究领域的热门问题，它不但具有理论价值，更具有重要的现实意义。连通性是图论中最重要的性质之一，基于这些方面，一种加强版的连通性概念——图的彩虹连通性的问题应运而生。在2008年，Chartrand、Johnson等人最先把这个概念引入到文献中。在过去的几年里，图的彩虹连通数一直作为图论中的热门问题受到众多

5、数学专家的广泛关注，同时也被应用到网络信息安全、密码学等领域。如果G是一个非平凡连通图，对G的边全部染上颜色。若用数字表示颜色，则c：E(G)_÷(1，2，⋯．kk∈J『＼『)即G为的一种着色方式。当经过图G中的一条路P上的边都被染成不同颜色时，则称路P为图G的一条彩虹路。如果对于连通图G来说，任意两点间都存在一条彩虹路，则称图G是彩虹连通的。称使得图G为彩虹路连通的所使用的最少颜色数k为图G的彩虹连通数，记为rc(G)。其后，Krivelevich和Yuster提出了彩虹顶点连通的概念。显然这是对图形的顶点进行染色。一个连通图的任意两个顶点之间至少存在一条内部顶点染

6、成不同颜色的路相连，则称该图是彩虹顶点连通的。类比图的彩虹连通数的概念可知，彩虹顶点连通数就是使得连通图G彩虹顶点连通的所必须的起码的颜色数，记为rvc(G)。本文研究了一些特殊图的彩虹连通性的问题，主要结果如下：(1)介绍了彩虹连通性问题的基本概念和己有的结论。(2)利用数学归纳法、分类讨论思想，计算出了完全图刺图、圈的刺图、风车图的彩虹连通数及强彩虹连通数。(3)运用数学归纳法和分类讨论的的数学思想，将原有图进行推广，对一些日晕图的彩虹连通数问题进行了研究。(4)对3．连通图的彩虹顶点连通数进行了求解。关键词：特殊图；彩虹连通数；彩虹顶点连通数万方数据英文摘要AB

7、STRACTAstheoriginofthegraphtheory，thefamousKonigsbergBridgeProblem，promotesthedevelopmentofthegraphtheory．Thecoloringofagraphhasalwaysbeenahotissueinthefieldofgraphtheoryresearch．Itnotonlyhastheoreticalvalue，butalsohastheimportantpracticalsignificance．Moreover，theconnectivityis