收藏本站
188bet官方网址
《南开大学》 2014年
收藏 | 手机打开
二维码
手机客户端打开本文

关于图的彩虹(顶点)连通数若干问题的研究

陈莉莉  
【摘要】:设图G是一个具有边染色的非平凡连通图,其中相邻边可以染相同颜色。称图G的一条路是彩虹路,如果这条路上的任意两条边都染不同颜色。如果对图G的任意两个顶点u和v,都存在一条彩虹路连接u和v,则称图G是彩虹连通的。使得图G是彩虹连通的所需的最少颜色数称为图G的彩虹连通数,用rc(G)表示。 彩虹连通数的概念是由Chartrand等人在2008年提出来的。它可以看成是连通度的加强,因为如果一个图是彩虹连通的,那么它显然是连通的。彩虹连通数概念的提出来源于政府机构之间的信息传递。当我们在机构之间传递信息时,为了安全,我们需要足够多的密码,使得任意两个机构之间都至少存在一条信息传递路,并且这条路上的每段被分配一个不同的密码。另一方面,我们又希望所用的密码尽可能的少。如果我们用图来表示这个信息传递网,用边染色表示密码,那么这个最少的密码数就是我们所说的彩虹连通数。 Krivelevich和Yuster接着提出了彩虹顶点连通数的概念。设图G是一个具有顶点染色的非平凡连通图。称图G的一条路是彩虹顶点连通路,如果这条路的内部顶点都染不同颜色。如果对图G的任意两个顶点u和v,都存在一条彩虹顶点连通路连接u和v,则称图G是彩虹顶点连通的。使得图G是彩虹顶点连通的所需的最少颜色数称为图G的彩虹顶点连通数,用ruc(G)表示。 本论文分为三章。在第一章中,我们介绍了彩虹连通数和彩虹顶点连通数的定义和背景,同时给出了本文要用到的一些概念和记号。我们还给出了关于彩虹连通数和彩虹顶点连通数的一些相关结果,其中包括本文的主要研究成果。 图的Nordhaus-Gaddum界是指图G的某个参数值和这个图的补图G对应的参数值的和或积的上下界。1956年,Nordhaus和Gaddum给出了关于图的色数的这种类型的上下界。自此,许多学者开始研究各种图参数的这种类型的界,并把该类型的界称为Nordhaus-Gaddum界。在第二章中,我们研究了图的彩虹连通数和彩虹顶点连通数这两个图参数的Nordhaus-Gaddum界。首先,我们研究彩虹连通数的Nordhaus-Gaddum界。我们用归纳法证明了rc(G)+rc(G)≤n+2,其中n为图G的顶点数,并且对每一个n(n≥4),这个上界是紧的。对于每个非完全图G,有rc(G)≥2,所以rc(G)+rc(G)≥4。我们证明当n≥8时,这个下界是紧的,而对4≤n≤7,我们得到更好的下界。当n=4,5时,rc(G)+rc(G)≥6,当n=6,7时,rc(G)+rc(G)≥5,且这些界都是紧的。类似的,我们给出图的彩虹顶点连通数的Nordhaus-Gaddum界。我们证明了对所有n≥5,2≤ruc(G)+rvc(G)≤n-1,并且这些界是紧的。 在第三章中,我们对图的彩虹顶点连通数的复杂性进行了研究。Caro等人猜想计算任意一个图的彩虹连通数是NP-困难的,甚至判定一个图的彩虹连通数是否为2都是NP-完全的。Chakraborty等人解决了这个猜想,并且还证明了给定一个边染色图G,判定图G在该染色下是否是彩虹连通的是NP-完全的。这些复杂性结论是对彩虹连通数进行的研究,受此启发,我们考虑了图的彩虹顶点连通数的复杂性。我们证明了判定一个图的彩虹顶点连通数是否为2是NP-完全的,因此计算一个图的彩虹顶点连通数是NP-困难的。同样我们也证明了判定一个给定顶点染色的图是否是彩虹顶点连通的是NP-完全的。在Chakraborty等人的文章中,他们只证明判定彩虹连通数是否为2是NP-完全的,但对任意固定的整数k(k≥3),判定rc(G)≤k是否是NP-完全的,他们并没有给出证明,他们猜想这个问题是NP-困难的。P.Ananth和M.Nasre证明了这个猜想。类似的,我们研究判定ruc(G)≤k这个问题的复杂性,我们证明该问题是NP-困难的,同时还证明这个问题属于NP类,因此它是NP-完全的。
【学位授予单位】:南开大学
【学位级别】:博士
【学位授予年份】:2014
【分类号】:O157.5

手机知网App
【参考文献】
中国期刊全文数据库 前1条
1 Jiu-ying DONG;Xue-liang LI;;Upper Bound Involving Parameter σ_2 for the Rainbow Connection Number[J];Acta Mathematicae Applicatae Sinica(English Series);2013年04期
【共引文献】
中国期刊全文数据库 前3条
1 陈其;金素萍;徐佳衡;杨双双;;基于彩虹着色的网络安全研究[J];科技创新与应用;2014年15期
2 王万禹;;图的修正的彩虹顶点连通数[J];山东大学学报(理学版);2015年02期
3 Jiu-ying DONG;Xue-liang LI;;Upper Bound Involving Parameter σ_2 for the Rainbow Connection Number[J];Acta Mathematicae Applicatae Sinica(English Series);2013年04期
中国博士188bet全文数据库 前4条
1 黄小龙;平面图和线图上的彩虹连通性研究[D];南开大学;2013年
2 李恒哲;图的彩虹连通数与距离[D];南开大学;2013年
3 董九英;图的彩虹连通数的若干上界[D];南开大学;2013年
4 刘素娟;2-(边-)连通图的彩虹连通数[D];南开大学;2013年
中国硕士188bet全文数据库 前2条
1 郭晶晶;图的无符号拉普拉斯特征值[D];浙江师范大学;2013年
2 郭泽;关于彩虹图的一些结果[D];华东师范大学;2014年
【相似文献】
中国博士188bet全文数据库 前3条
1 陈莉莉;关于图的彩虹(顶点)连通数若干问题的研究[D];南开大学;2014年
2 李恒哲;图的彩虹连通数与距离[D];南开大学;2013年
3 董九英;图的彩虹连通数的若干上界[D];南开大学;2013年
中国知网广告投放
相关机构
>南开大学
相关作者
>董九英 >李恒哲
>陈莉莉
 快捷付款方式  订购知网充值卡  订购热线  帮助中心
  • 400-819-9993
  • 010-62791813
  • 010-62985026