【作者】 黄小龙；

【导师】 李学良；

【作者基本信息】 南开大学 ， 应用数学， 2013， 博士

【摘要】 假设在一个蜂窝网络中,人们希望能在任意两个顶点之间传送信息,并且要求该线路上的每条边被分配不同的信道。那么,在满足上述要求的前提下,最少需要使用多少不同信道才能保证网络中任意两点之间能够传送信息?将该网络抽象成一个图,研究证明这个最小值就是该图的彩虹连通数。彩虹连通的概念由Chartrand等人于2008年提出。设G为一个非平凡的连通图。定义图G上的一个边染色c：E(G)→C,其中C={1,2,…,k｝,k∈N,表示k种不同颜色的集合,边染色c允许图G中相邻的边染同种颜色。图G的一条路是彩虹的,如果该路上每条边的颜色不同。给定图G的一个边染色,如果任意两个顶点之间存在一条彩虹路,则称图G在该染色下是彩虹连通的。同时称该边染色为彩虹染色。使得图G彩虹连通所需的最少颜色数称为彩虹连通数,记为rc(G)。在顶点染色图G中,如果一条路的内部顶点染的颜色都不相同,那么称该路是彩虹的。顶点染色图G是彩虹顶点连通的,如果任意两个不同顶点之间至少有一条彩虹路。这样的顶点染色称为彩虹顶点染色。连通图G的彩虹顶点连通数,记为rvc(G),是使得图G彩虹顶点连通所需的最少颜色数。彩虹顶点连通的概念首次由Krivelevich和Yuster提出。本文首先从算法复杂性的角度对彩虹(顶点)连通性进行了研究。对于一般图,Chakraborty等人证明了对于给定的边着色图(颜色数是任意的)判定该图是否彩虹连通是NP-完全的。对于特殊图类,给定一个边着色图G(颜色数是任意的)判定图G在该染色下是否彩虹连通,确定这个问题的复杂类别是很有意义的。事实上,特殊图类的复杂性研究能更好地帮助我们从算法的角度理解彩虹连通性。受此启发,我们研究了上述判定问题在平面图,以及平面二部图上的复杂性,证明了给定一个边染色平面图G,判定图G在该染色下是否彩虹连通是NP-完全的。更进一步地,我们证明了给定一个边染色平面二部图G,判定图G在该染色下是否彩虹连通仍然是NP-完全的。对于彩虹顶点连通性的复杂性问题,本文研究了如下判定问题：给定一个顶点染色线图,判定该图是否顶点彩虹连通。我们证明了该判定问题是NP-完全的。相对于目前已有的结果,我们的结论则更强。其次,本文研究了平面图的彩虹连通数的上界问题。作为图论中一个相当大的图类,平面图的彩虹连通数的上界研究还是空白。一个自然的问题就是：给定一个平面图G,确定rc(G)的上界。我们给出了无桥平面图的彩虹连通数的上界,具体地,当直径为2时,无桥外平面图G的彩虹连通数满足2≤rc(G)≤3,并且上界是紧的；当直径为3时,无桥外平面图G的彩虹连通数满足3≤rc(G)≤6。因此这个结果部分地回答了上述问题。本文由四部分组成。在第一章中我们首先介绍了彩虹(顶点)连通的背景,一些术语和概念,其次概述了相关的结果以及本文的主要结论。在第二章中我们证明了：给定一个边染色平面图G,判定图G在该染色下是否彩虹连通是NP-完全的。更进一步地,我们证明了：给定一个边染色平面二部图G,判定图G在该染色下是否彩虹连通是NP-完全的。在第三章中我们着重研究了无桥外平面图的彩虹连通数的上界。当直径为2时,无桥外平面图G的彩虹连通数满足2≤rc(G)≤3；当直径为3时,无桥外平面图G的彩虹连通数满足3≤rc(G)≤6。在第四章中我们证明了：给定一个顶点染色线图L(G),判定图L(G)在该染色下是否彩虹顶点连通是NP-完全的。更多还原

【Abstract】 Suppose in a cellular network, people wish to transfer messages between any two vertices in a route, and require that each edge on the route between the vertices is assigned a distinct channel. In order to transfer messages between any two vertices, what is the minimum number of distinct channels that we use in network? This number is precisely the rainbow connection number, which was introduced by Chartrand et al. in2008.Let G be a nontrivial connected graph. An edge coloring of G is a function c:E(G)→C, where C={1,2,..., k}, is a set of k different colors. In such coloring, adjacent edges may have the same color. A path in G is called rainbow if no two edges of the path share the same color. An edge-colored graph G is rainbow connected if for every pair of distinct vertices u and v of G, there exists at least one rainbow path in G joining u and v. An edge-coloring which makes G rainbow connected is called a rainbow coloring of G. The rainbow connection number of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected.A vertex-colored graph is rainbow vertex-connected if every two vertices are connected by a path whose internal vertices have distinct colors (such path is called vertex rainbow path). The rainbow vertex-connection number of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. The definition of rainbow vertex-connection was proposed by Krivelevich and Yuster.First of all, we start the research of rainbow (vertex-) connection from its algorithmic aspects. For general graphs, Chakraborty et al. proved that given an edge-colored graph G, checking whether the given coloring makes G rainbow connected is NP-complete. In fact, the investigation on special graphs could help us understand the behavior of rainbow connection better. Therefore, we consider the following decision problem for special graph classes:what is the complexity of deciding whether a given edge-coloured graph G is rainbow connected (with an unbounded number of colors)? Motivated by this challenge, we study the decision problem for planar graphs and planar bipartite graphs. We prove that given an edge-colored planar graph G, checking whether the given coloring makes G rainbow connected is NP-complete. Furthermore, we prove that given an edge-colored planar bipartite graph G, checking whether the given coloring makes G rainbow connected is NP-complete.For rainbow vertex connection, analogously, what is the complexity of decid-ing whether a given vertex-coloured graph G is rainbow vertex connected? We consider line graphs, and prove that this decision problem is NP-complete. This is a stronger result than previous related work.Secondly, we compute the upper bounds for rainbow connection number of planar graphs. Planar graphs are a very large graph class, but there are few results of rainbow connection number of planar graphs. A natural problem arise:given a planar graph G, find good upper bounds for the rainbow connection number rc(G). This thesis investigates upper bounds for rainbow connection number of bridgeless outerplanar graphs. Let G be a bridgeless outerplanar graph. If G has diameter two, then rc(G)≤3; if G has diameter three, then rc(G)≤6. Those results answer the above problem partially.This thesis consists of four chapters.In Chapter1, we provide the required background of rainbow (vertex-) con-nection, and list some terminology and notations. We also give an overview of results on rainbow (vertex-) connection including the main results of this thesis. In Chapter2, we prove that deciding if a given edge-colored planar graph is rainbow connected is NP-complete. Furthermore, we prove that it is still NP-complete even when the edge-colored graph is a planar bipartite graph.In Chapter3, we focus on the bridgeless outerplanar graphs and compute the upper bounds of rainbow connection numbers. In particular, let G be a bridgeless outerplanar graph. If diam(G)=2, then rc(G)<3, this bound is sharp; if diam(G)=3, then rc(G)≤6.In Chapter4, we show that deciding if a given vertex-colored line graph is rainbow vertex-connected is NP-complete.更多还原