平面图和线图上的彩虹连通性研究

摘要

假设在一个蜂窝网络中，人们希望能在任意两个顶点之间传送信息，并且要求该线路上的每条边被分配不同的信道。那么，在满足上述要求的前提下，最少需要使用多少不同信道才能保证网络中任意两点之间能够传送信息？将该网络抽象成一个图，研究证明这个最小值就是该图的彩虹连通数。彩虹连通的概念由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

Contents

Chapter 1 Introduction

1．1 Background and Notation

1．2 Overview of Results

1．3 Organization of the Dissertation

Chapter 2 Rainbow Connection for Planar Graphs

2．1 Preliminaries

2．2 Rainbow Connection for Planar Graphs

2．3 Rainbow Connection for Planar Bipartite Graphs

2．4 Concluding and Open Problems

Chapter 3 Outerplanar Graphs with Small Diameter

3．1 Preliminaries

3．2 Outerplanar Graphs with Diameter 2

3．3 Outerplanar Graphs with Diameter 3

Chapter 4 Rainbow Vertex-connection for Line Graphs

4．1 Preliminaries

4．2 Previous and Related Work

4．3 Rainbow Vertex-connection for Line Graphs

Bibliography

致谢

个人简介