关于图的正常（强）彩虹连通数和正常（强）彩虹顶点连通数的若干结果.pdf

摘要

染色问题是图论研究中的热门课题之一.2008年,Chartrand等人提出的彩虹连通数在

网络安全方面起了重要的作用,至此彩虹染色问题开始走进人们的视野,被国内外众多专家

学者广泛关注.作为一个自然推广,彩虹顶点连通数,全彩虹连通数及正常(强)彩虹连通数

等概念先后被提出.本文我们提出了正常(强)彩虹顶点连通数的概念,并对图的正常(强)彩

虹连通数和正常(强)彩虹顶点连通数进行了若干研究.

本文共包括四章.第1章,我们给出了文中需要用到的符号和术语,并且介绍了彩虹染

色及其相关问题的概念与背景.

第2章,我们研究了所有顶点数为8或者更少的三度正则图,铅笔图,circularladders

¨

图以及Mobiusladders图的正常(强)彩虹连通数.此外,我们研究了具有较大团数n−1和

n−2的图的正常(强)彩虹连通数.同时,我们探究了具有较大团数n−3的图的正常(强)彩

虹连通数与其边色数之间的关系.

第3章,我们首先确定了所有顶点数为8或者更少的三度正则图,路,圈,轮图,完全多

¨

部图,铅笔图,circularladders图以及Mobiusladders图的正常(强)彩虹顶点连通数.此外,

我们修正了Simamora等人的主要结果:当n2468或者n是奇数时,rvc(Pc)⌈n⌉;当

n2

n

n≥10且n是偶数时,rvc(Pc)⌈⌉1.其次,我们确定了具有较大团数n−1,n−2和n−3

n2

的图的正常(强)彩虹顶点连通数.最后,对于一个n阶连通图G,我们刻画了prvc(G)n和

prvc(G)n−1的所有图类.

第4章,我们总结了本文的研究结果,并提出了后续的研究方向.

关键词:彩虹染色,彩虹顶点染色,正常(强)彩虹连通数,正常(强)彩虹顶点连通数

I

ABSTRACT

Theproblemofgraphcoloringisoneofthehottopicsofgraphtheoryresearch.In2008,

Chartrandetal.proposedtherainbowconnectionnumberthatplaysanimportantroleinnetwork

security.Sofar,theproblemofrainbowcoloringhascomeintopeople’sviewandbeenwidely

concernedbymanyexpertsandscholarsathomeandabroad.Asanaturalgeneralization,the

conceptsofrainbowvertexconnectionnumber,totalrainbowconnectionnumberandproper

(strong)rainbowconnectionnumberhavebeenproposedsuccessively.Inthispaper,wepropose

theconceptofproper(strong)rainbowvertexconnectionnumber,andinvestigatetheproper

(strong)rainbowconnectionnu