2-（边-）连通图的彩虹连通数

摘要

2008年，Chartrand，Johns，McKeon和Zhang首次提出了图的彩虹连通性的概念，经典连通性概念的一种加强。令G为一个非平凡的连通图，在G上定义一个边染色c:E(G)→｛1，2，…，k｝，k∈N，其中相邻的边可能染同种颜色。图G的一条路是彩虹的，如果这条路上的边分别染不同的颜色。如果边染色图G的任意两个不同顶点之间至少有一条彩虹路，我们就称G是彩虹连通的。使得图G彩虹连通的边染色被称为彩虹染色。使得图G彩虹连通所需的最少的颜色数称为G的彩虹连通数，记为rc(G)。显然，彩虹连通图一定是连通的，且将所有边染不同颜色可以得到连通图的一个彩虹染色。
　　作为一个自然的组合概念，彩虹连通数不仅有其理论意义，而且在网络问题中有着重要的应用。事实上，这些概念产生于政府机构之间机密信息安全传输的问题。假设我们需要在一个蜂窝网络中传输信息。网络中的任意两点都有一条路连接，并且该路上的每段被分配一个独特的频道（例如，不同的频率）。显然，我们要求网络中所使用的不同频道的个数最少。而这个最少个数恰是网络所对应无向图的彩虹连通数。
　　Menger定理指出一个图是k-连通的当且仅当它的任意两个不同顶点之间都有k条内部不交的路相连。下面给出彩虹连通的一个自然的推广。令G是一个(e)-连通的边染色图。对任意整数k（1≤k≤(e))图G是彩虹k-连通的，如果G的任意两个不同顶点之间都有k条内部不交的彩虹路。图G的彩虹k-连通数rck(G)定义为最小的整数t使得存在图G的一个t种颜色的边染色，在这种染色下图G是彩虹k-连通的。根据定义，rck(G)是rc(G)的一个推广，并且rc1(G)=rc(G)。Menger定理还证明了:一个图是k-边连通的当且仅当它的任意两个不同顶点之间都有k条边不交的路相连。令G是一个(e)-边连通的边染色图。对任意k∈N（1≤k≤(e)），我们称图G是彩虹k-边连通的，如果对G的任意两个不同顶点u和v，存在至少k条边不交的彩虹路连接u和v。并且这样的一个边染色称为图G彩虹k-边染色。图G的彩虹k-边连通数，记为rc'k(G)，是最小的整数j使得存在图G的一个j种颜色的边染色，在这种染色下G是彩虹k-边连通的。
　　Krivelevich和Yuster首次提出了彩虹顶点连通的概念。在顶点染色图G中，一条路是彩虹的，如果它的内部顶点染不同的颜色。顶点染色图G是彩虹顶点连通的，如果它的任意两个不同顶点之间至少有一条彩虹路连接。并且这样的顶点染色称为彩虹顶点染色。连通图G的彩虹顶点连通数，记为rvc(G)，是使得G彩虹顶点连通所需的最少的颜色数。注意到边染色图中的彩虹路不同于点染色图中的彩虹路。
　　本文共包括五章。在第1章中，我们介绍了彩虹连通的定义和背景，并给出了本文中用到的一些符号和术语。我们还对彩虹连通相关的一些结论做了概述，其中包括本文的主要结论。
　　在第2章中，我们讨论了在本文主要结论的证明过程中需要用到的一些预备知识和彩虹连通的简单性质。
　　在第3章中，我们首先给出了一个新概念—非完全彩虹染色，并利用它证明了:任意n阶2-连通图G都有一个至多[n/2]种颜色的彩虹边染色，即rc(G)≤[n/2]。其次，刻划了一些彩虹连通数为[n/2]的n阶哈密尔顿图类。最后，我们证明:任意n阶含割点的连通图G的彩虹连通数小于等于(n+r-1)/2，其中r是图G中偶块的个数。在此基础上，还证明了阶数为n（n≥3）的2-边连通图G的彩虹连通数一个紧的上界，即rc(G)≤{2k ifn=3k+1or3k+22k+1 ifn=3k+3Fujita，Liu和Magnant在[35,37]中提出了一个问题:使得任意n阶2-连通图G都满足条件rc2(G)≤αn的最小的常数α是多少？在第4章中，我们给出了上述问题的答案:α=1，并且rc2(G)=n当且仅当G是一个n阶的圈。作为一个推广，我们给出了图G的彩虹k-边连通数的概念，记作rc'k(G)。我们还证明了:如果n阶图G是2-边连通的，那么rc'2(G)≤n，且等号成立当且仅当G是一个n阶的圈。
　　在第5章中，我们首先确定了n（n≥3）阶圈Cn的彩虹顶点连通数，并证明了:对任意n阶2-连通图G，rvc(G)≤rvc(Cn)，即给出了2-连通图彩虹顶点连通数一个紧的上界。由此我们得到:如果连通图G的块分解为B1，B2，…，Bk且含有t个割点，则有rvc(G)≤rvc(B1)+rvc(B2)+…+rvc（Bk）+t。我们还刻划了所有具有彩虹顶点连通数[n/2]的n阶哈密尔顿图。