设图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的彩虹顶点连通数，用rvc(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≤rvc(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证明了这个猜想。类似的，我们研究判定rvc(G)≤k这个问题的复杂性，我们证明该问题是Np-困难的，同时还证明这个问题属于Np类，因此它是Np-完全的。