图的彩虹连通数的若干上界
|
摘要
令G=(V(G),E(G))是一个简单无向有限图,其中V(G)是G的顶点集,E(G)是G的边集。在2006年,Chartrand等人引进了一种关于彩虹边着色的新概念。其定义如下：G的一个k边着色是一个映射c:E(G)→C,其中C是k种不同颜色的集合。令G是一个边着色图。如果G中一条路的每条边都着有不同的颜色,我们称这条路为G的彩虹路。如果G的任意两个顶点间都存在一条彩虹路连通它们,我们称G为彩虹连通。如果一个边着色使G彩虹连通,那么我们称该着色为彩虹着色。我们把G的彩虹着色所需的最小颜色数称为G的彩虹连通数,记为rc(G)。从彩虹连通的定义,我们能看到一个彩虹连通图的两条相邻的边可以着相同的颜色。以上的着色定义在一个图的边集上,自然地,我们可以把以上的着色推广到图G的顶点集上。在2008年,Krivelevich和Yuster引进了彩虹点着色的概念,类似地给出了点彩虹着色、点彩虹路、点彩虹连通,点彩虹连通数rvc(G)的定义。
根据rc(G)和rvc(G)的定义,Chartrand等人计算出了一些特殊图类的彩虹连通数。然而,对于一般图来说,计算它们的彩虹连通数是一件非常困难的事情。Chakraborty等人证明：对于一个给定的图G,确定rc(G)是否等于2是NP-完全的。特别地,他们证明：计算rc(G)是NP-困难的。于是他们解决了Caro等人提出来的猜想。因此,研究一个图的彩虹连通数的上界成为人们感兴趣的问题。
本文分为六章。在第一章中,我们介绍了本文所需要的概念,本文的研究背景和主要结果。
在第二章中,我们研究了彩虹连通数关于最小度和的上界.Krivelevich和Yuster证明：假如G是一个δ(G)≥3且阶为n的连通图,那么且后来,Chandran等人改进了Krivelevich和Yuster的方法,得到了一个更好的结果。他们证明了假如G是一个δ(G)≥3且阶为n的连通图,那么rc(G)≤3n/(δ(G)+1)+3。我们考虑了彩虹连通数与最小度和的关系,推广了Chandran等人的结果。我们证明了如果G是一个阶为n且有k个独立顶点的连通图,那么另外,我们证明了如果G是一个阶为n且有k个独立顶点的连通图,假如σk(G)≤7k或σk(G)≥8k,那么假如7k<σk(G)<8k,那么我们举了一个例子,在这个例子中,我们的界是常数,而Krivelevich和Yuster的界、Chandran等人的界都是n的线性函数。在证明中我们应用了算法、Locasz局部引理以及概率的方法。
在第三章中,我们讨论了彩虹连通数与桥和半径的问题。Basavaraju等人考虑了无桥图的彩虹连通数和半径的关系。他们证明了假如G是一个半径为r的无桥图,那么rc(G)≤r(r+2).我们考虑了任意连通图的彩虹连通数与桥和半径的关系,证明了如果G是一个半径为r且中心点为u的连通图,令Dr={u},那么G有r-1个连通控制集Dr-1,Dr-2,…,D1满足Dr(?)Dr-1(?)Dr-2…(?)D1(?) Do=V(G)且有rc(G)≤∑ri=1max{2i+1,bi},其中对于每一个i∈[1,r]满足bi等于E[Di,N(Di)]中的桥数,并且G的桥数等于∑i~r=1bi。注意到假如对于所有的i∈[1,r]都满足bi≤2i+1,那么rc(G)≤∑ri=1(2i+1)=,(r+2);而假如对于所有的i∈[1,r]都满足bi>2i+1,那么rc(G)=∑ri=1bi。因此我们的结果本质上推广了Basavaraju等人的结果。
在第四章中,我们解决了Chakraborty等人提出的问题。Chakraborty等人提出：“我们能否用o(n)种颜色在多项式时间内对一个rc(G)=2的图进行彩虹着色?”为了解决这个问题,我们证明了两个结果。第一个结果是：我们能用至多5种颜色在多项式时间内对一个直径为2的无桥图进行彩虹着色。第二个结果是：我们能用至多4种颜色在多项式时间内对一个rc(G)=2的有桥图进行彩虹着色。因此我们能推出用至多5种颜色可以在多项式时间内对一个rc(G)=2的图进行彩虹着色。
在第五章中,我们讨论了稠密图的彩虹连通数并得到了几个概括性的结果。
在第六章中,我们研究了彩虹连通数与独立数的关系,证明了假如G是一个连通图,那么rc(G)≤2a(G)一1.我们举例子说明了存在图G满足G的直径等于2a(G)-1。即我们的结果达到了最好。然而,Chandran等人的界3n/(δ(G)+1)+3和[n÷2]都是n的线性函数,Schiermeyer的界也是n的线性函数,并且Basavaraju等人的界,r(r+2)是r平方级的,其远离G的直径。
Let G=(V(G),E(G)) be a simple undirected and finite graph, where V(G) is the set of vertices in G, and E(G) is the set of edges in G. In2006, Chartrand et al. introduced a new concept about rainbow edge-coloring. Its definition is as follows:A k-edge coloring of G is a mapping c:E(G)→C, where C is a set of k distinct colors. Let G be an edge-coloring graph. A path of G is called rainbow if every edge of it is colored by a distinct color. A graph G is called rainbow connected if G contains a rainbow u-v path for every two vertices u and v of G. An edge coloring is called a rainbow-coloring if this coloring makes G rainbow connected. The rainbow connection number rc(G) is defined as the smallest number of colors that are needed to make G rainbow connected. From the definition of rainbow connection, we can see that two adjacent edges of a rainbow-connected graph may be colored by the same color. The above coloring is defined in the edges of a graph, and a nature idea is to generalize the coloring to the vertices of a graph. In2008, Krivelevich and Yuster introduced the notion of rainbow vertex-coloring, and similarly gave out the definitions of vertex-rainbow coloring, vertex-rainbow path, rainbow vertex-connection and rainbow vertex-connection number rvc(G).
According to the definition of rainbow connection number, Chartrand et al. com-puted the rainbow connection numbers about some special graph classes. However, computing the rainbow connection number for a general graph is a very difficult thing. Chakraborty et al. showed that for a given graph G deciding if rc(G)=2is NP-complete. In particular, they showed that computing rc(G) is NP-hard, which were conjectured by Caro et al. So finding the upper bound for rainbow-connection number rc(G) or rvc(G) of a graph is an interesting problem.
In Chapter2, we study the upper bound for rainbow connection number involving the minimum degree sum, and get two generalized results. Krivelevich and Yuster showed that if G is a connected graph of order n with minimum degree8(G) then rc(G)<-20n/δ(G) and rvc(G)<11n/δ(G). Later, Chandran et al. improved the technique of Krivelevich and Yuster, and got a better result. They showed that if G is a connected graph of order n and minimum degree8(G), then rc(G)≤3n/(8(G)+1)+3. We consider the relation between the rainbow connection number and minimum degree sum, and get a generalized result. We show that if G is a connected graph of order n with k independent vertices, then In addition, we show that if G is a connected graph of order n with k independent vertices, then rvc(if σk(G)≤7k or σt(G)≥8k; whereas rvc We give an example G to show that our bounds are constants; whereas the bounds of Chandran et al., Krivelevich and Yuster are all liner in n. Algorithms, Lovasz Local Lemma and the probabilistic method are applied in the proofs of the above two results.
In Chapter3, we discuss the problem of rainbow connection number relating to bridges and radius. Basavaraju et al. considered the relation between rainbow connec-tion number and radius in a bridgeless graph. They proved that if G is a bridgeless graph with radius r, then rc(G)≤r(r+2). An example was given to show that the bound is tight. We study the rainbow connection number involving bridges and ra-dius in a general graph, and get the following result:If G is a connected graph with radius r and center vertex u. Let Dr={u}, then G has r-1connected dominat-ing sets Dr-1,Dr-2,…,D1such that Dr(?)Dr-1C Dr-2…(?)D1(?) D0=V(G) and rc(G)≤∑ri=1max{2i+1,bi}, bi is the number of bridges in E[Di,N(Di)] for1≤i≤r, and the number of bridges in G is equal to∑ri=1bi. Note that if bi≤2i+1for all1≤i≤r, then rc(G)≤∑ri=i(2i+1)=r(r+2); whereas if bi>2i+1for all1≤i≤r, then rc(G)=∑ri=1bi. So our result substantially generalizes the result of Basavaraju et al.
In Chapter4, we contribute to the question proposed by Chakraborty et al.. Chakraborty et al. questioned:"If we are given a graph G for which we are told that rc(G)=2, can we rainbow-color it in polynomial time with o(n) colors?" To solve this problem, we show two results. The first one is that for any bridgeless graph G with diameter2we can rainbow-color G in polynomial time by at most5colors. The second one is that for any graph G with bridges satisfying rc(G)=2we can rainbow-color G in polynomial time by at most4colors. According to the above two results, we solve completely the question proposed by Chakraborty et al.
In Chapter5, we discuss the rainbow connection number of dense graphs, and obtain several generalized results.
In Chapter6, we study the relation of rainbow connection number and indepen-dence number, and get a good upper bound of rainbow connection number. We ob-tain that if G is a connected graph, then rc(G)≤2a(G)-1. Examples are given to show that our bound2a(G)-1is the best possible, because it is equal to the di-ameter of graphs in examples. However, the upper bounds of Chandran et al. are3n/(8(G)+1)+3=3n/4+3and [n/2], the upper bound of Schiermeyer is They are liner in n, and the bound of Basavaraju et al. is r(r+2), far from the diameter of G.
根据rc(G)和rvc(G)的定义,Chartrand等人计算出了一些特殊图类的彩虹连通数。然而,对于一般图来说,计算它们的彩虹连通数是一件非常困难的事情。Chakraborty等人证明：对于一个给定的图G,确定rc(G)是否等于2是NP-完全的。特别地,他们证明：计算rc(G)是NP-困难的。于是他们解决了Caro等人提出来的猜想。因此,研究一个图的彩虹连通数的上界成为人们感兴趣的问题。
本文分为六章。在第一章中,我们介绍了本文所需要的概念,本文的研究背景和主要结果。
在第二章中,我们研究了彩虹连通数关于最小度和的上界.Krivelevich和Yuster证明：假如G是一个δ(G)≥3且阶为n的连通图,那么且后来,Chandran等人改进了Krivelevich和Yuster的方法,得到了一个更好的结果。他们证明了假如G是一个δ(G)≥3且阶为n的连通图,那么rc(G)≤3n/(δ(G)+1)+3。我们考虑了彩虹连通数与最小度和的关系,推广了Chandran等人的结果。我们证明了如果G是一个阶为n且有k个独立顶点的连通图,那么另外,我们证明了如果G是一个阶为n且有k个独立顶点的连通图,假如σk(G)≤7k或σk(G)≥8k,那么假如7k<σk(G)<8k,那么我们举了一个例子,在这个例子中,我们的界是常数,而Krivelevich和Yuster的界、Chandran等人的界都是n的线性函数。在证明中我们应用了算法、Locasz局部引理以及概率的方法。
在第三章中,我们讨论了彩虹连通数与桥和半径的问题。Basavaraju等人考虑了无桥图的彩虹连通数和半径的关系。他们证明了假如G是一个半径为r的无桥图,那么rc(G)≤r(r+2).我们考虑了任意连通图的彩虹连通数与桥和半径的关系,证明了如果G是一个半径为r且中心点为u的连通图,令Dr={u},那么G有r-1个连通控制集Dr-1,Dr-2,…,D1满足Dr(?)Dr-1(?)Dr-2…(?)D1(?) Do=V(G)且有rc(G)≤∑ri=1max{2i+1,bi},其中对于每一个i∈[1,r]满足bi等于E[Di,N(Di)]中的桥数,并且G的桥数等于∑i~r=1bi。注意到假如对于所有的i∈[1,r]都满足bi≤2i+1,那么rc(G)≤∑ri=1(2i+1)=,(r+2);而假如对于所有的i∈[1,r]都满足bi>2i+1,那么rc(G)=∑ri=1bi。因此我们的结果本质上推广了Basavaraju等人的结果。
在第四章中,我们解决了Chakraborty等人提出的问题。Chakraborty等人提出：“我们能否用o(n)种颜色在多项式时间内对一个rc(G)=2的图进行彩虹着色?”为了解决这个问题,我们证明了两个结果。第一个结果是：我们能用至多5种颜色在多项式时间内对一个直径为2的无桥图进行彩虹着色。第二个结果是：我们能用至多4种颜色在多项式时间内对一个rc(G)=2的有桥图进行彩虹着色。因此我们能推出用至多5种颜色可以在多项式时间内对一个rc(G)=2的图进行彩虹着色。
在第五章中,我们讨论了稠密图的彩虹连通数并得到了几个概括性的结果。
在第六章中,我们研究了彩虹连通数与独立数的关系,证明了假如G是一个连通图,那么rc(G)≤2a(G)一1.我们举例子说明了存在图G满足G的直径等于2a(G)-1。即我们的结果达到了最好。然而,Chandran等人的界3n/(δ(G)+1)+3和[n÷2]都是n的线性函数,Schiermeyer的界也是n的线性函数,并且Basavaraju等人的界,r(r+2)是r平方级的,其远离G的直径。
Let G=(V(G),E(G)) be a simple undirected and finite graph, where V(G) is the set of vertices in G, and E(G) is the set of edges in G. In2006, Chartrand et al. introduced a new concept about rainbow edge-coloring. Its definition is as follows:A k-edge coloring of G is a mapping c:E(G)→C, where C is a set of k distinct colors. Let G be an edge-coloring graph. A path of G is called rainbow if every edge of it is colored by a distinct color. A graph G is called rainbow connected if G contains a rainbow u-v path for every two vertices u and v of G. An edge coloring is called a rainbow-coloring if this coloring makes G rainbow connected. The rainbow connection number rc(G) is defined as the smallest number of colors that are needed to make G rainbow connected. From the definition of rainbow connection, we can see that two adjacent edges of a rainbow-connected graph may be colored by the same color. The above coloring is defined in the edges of a graph, and a nature idea is to generalize the coloring to the vertices of a graph. In2008, Krivelevich and Yuster introduced the notion of rainbow vertex-coloring, and similarly gave out the definitions of vertex-rainbow coloring, vertex-rainbow path, rainbow vertex-connection and rainbow vertex-connection number rvc(G).
According to the definition of rainbow connection number, Chartrand et al. com-puted the rainbow connection numbers about some special graph classes. However, computing the rainbow connection number for a general graph is a very difficult thing. Chakraborty et al. showed that for a given graph G deciding if rc(G)=2is NP-complete. In particular, they showed that computing rc(G) is NP-hard, which were conjectured by Caro et al. So finding the upper bound for rainbow-connection number rc(G) or rvc(G) of a graph is an interesting problem.
In Chapter2, we study the upper bound for rainbow connection number involving the minimum degree sum, and get two generalized results. Krivelevich and Yuster showed that if G is a connected graph of order n with minimum degree8(G) then rc(G)<-20n/δ(G) and rvc(G)<11n/δ(G). Later, Chandran et al. improved the technique of Krivelevich and Yuster, and got a better result. They showed that if G is a connected graph of order n and minimum degree8(G), then rc(G)≤3n/(8(G)+1)+3. We consider the relation between the rainbow connection number and minimum degree sum, and get a generalized result. We show that if G is a connected graph of order n with k independent vertices, then In addition, we show that if G is a connected graph of order n with k independent vertices, then rvc(if σk(G)≤7k or σt(G)≥8k; whereas rvc We give an example G to show that our bounds are constants; whereas the bounds of Chandran et al., Krivelevich and Yuster are all liner in n. Algorithms, Lovasz Local Lemma and the probabilistic method are applied in the proofs of the above two results.
In Chapter3, we discuss the problem of rainbow connection number relating to bridges and radius. Basavaraju et al. considered the relation between rainbow connec-tion number and radius in a bridgeless graph. They proved that if G is a bridgeless graph with radius r, then rc(G)≤r(r+2). An example was given to show that the bound is tight. We study the rainbow connection number involving bridges and ra-dius in a general graph, and get the following result:If G is a connected graph with radius r and center vertex u. Let Dr={u}, then G has r-1connected dominat-ing sets Dr-1,Dr-2,…,D1such that Dr(?)Dr-1C Dr-2…(?)D1(?) D0=V(G) and rc(G)≤∑ri=1max{2i+1,bi}, bi is the number of bridges in E[Di,N(Di)] for1≤i≤r, and the number of bridges in G is equal to∑ri=1bi. Note that if bi≤2i+1for all1≤i≤r, then rc(G)≤∑ri=i(2i+1)=r(r+2); whereas if bi>2i+1for all1≤i≤r, then rc(G)=∑ri=1bi. So our result substantially generalizes the result of Basavaraju et al.
In Chapter4, we contribute to the question proposed by Chakraborty et al.. Chakraborty et al. questioned:"If we are given a graph G for which we are told that rc(G)=2, can we rainbow-color it in polynomial time with o(n) colors?" To solve this problem, we show two results. The first one is that for any bridgeless graph G with diameter2we can rainbow-color G in polynomial time by at most5colors. The second one is that for any graph G with bridges satisfying rc(G)=2we can rainbow-color G in polynomial time by at most4colors. According to the above two results, we solve completely the question proposed by Chakraborty et al.
In Chapter5, we discuss the rainbow connection number of dense graphs, and obtain several generalized results.
In Chapter6, we study the relation of rainbow connection number and indepen-dence number, and get a good upper bound of rainbow connection number. We ob-tain that if G is a connected graph, then rc(G)≤2a(G)-1. Examples are given to show that our bound2a(G)-1is the best possible, because it is equal to the di-ameter of graphs in examples. However, the upper bounds of Chandran et al. are3n/(8(G)+1)+3=3n/4+3and [n/2], the upper bound of Schiermeyer is They are liner in n, and the bound of Basavaraju et al. is r(r+2), far from the diameter of G.
引文
[1]A. Ahadi, A. Dehghan, On rainbow connection of strongly regular graphs, arX-iv:1001.3413v1 [math. CO] 2010.
[2]N. Alon, R. Duke, H. Lefmann, V. Rodl, R. Yuster, The algorithmic aspects of the Regularity lemma, J. Algorithms,16(1994),80-109.
[3]N. Alon, J.H. Spencer, The Probabilistic Method,3rd ed, Wiley, New York,2008.
[4]P. Ananth, M. Nasre, New hardness results in rainbow connectivity, arX-iv:1104.2074v1[cs.CC]2011.
[5]M. Basavaraju, L.S. Chandran, D. Rajendraprasad, A. Ramaswamy, Rainbow connection number and radius, Graphs Combin., in press.
[6]J.A. Bondy, U.S.R. Murty, Graph Theory, GTM244, Springer, Berlin(2008).
[7]B. Bollobas, A. Thomason, Threshold functions, Combinatorica,7(1986),35-38.
[8]Y. Caro, A. Lev, Y. Roditty, Z. Tuza, R. Yuster, On rainbow connection, Electron. J. Combin.,15(2008), R57.
[9]S. Chakraborty, E. Fischer, A. Matsliah, Yuster, Hardness and algorithms for rain-bow connection, J. Combin. Optimization,21(2011),330-347.
[10]L.S. Chandran, A. Das, D. Rajendraprasad, N.M. Varma, Rainbow connection number and connected dominating sets, J. Graph Theory,71(2012),206-218.
[11]L.S. Chandran, X. Li, S. Liu, R. Mathew, D. Rajendraprasad, Rainbow connection number and connectivity, Electron. J. Combin.,19(2012), P20.
[12]G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang, Rainbow connection in graph-s, Math. Bohem.,133(2008),85-98.
[13]G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang, The rainbow connectivity of
a graph, Networks,54(2)(2009),75-81.
[14]G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang, On the rainbow connectivity of cages, Congr. Numer.184(2)(2007),209-222.
[15]L. Chen, X. Li, M. Liu, Nordhaus-Gaddum-type theorem for the rainbow vertex-connection number of a graph, Util. Math.86(2011),335-340.
[16]X. Chen, X. Li, A solution to a conjecture on the rainbow connection number, Ars Combin.104(2012),193-196.
[17]J. Dong, X. Li, Upper bound involving parameter σ2(G) for the rainbow connec-tion, accepted by Acta Math. Appl. Sin.(English edition).
[18]J. Dong, X. Li, Rainbow connection numbers and the minimum degree sum of a graph, Science in China Series A, Mathematics,43 (2013),7-14(in Chinese).
[19]J. Dong, X. Li, Rainbow connection numbers, bridges and radius, Graphs Com-bin., in press, doi:10.1007/s00373-012-1218-3.
[20]J. Ekstein, P. Holub, T. Kaiser, M. Koch, S.M. Camacho, Z. Ryjacek, I. Schier-meyer, The rainbow connection number of 2-connected graphs, Discrete Math., in press.
[21]A. Frieze, C.E. Tsourakakis, Rainbow connectivity of sparse random graphs, arX-iv:1201.4603v2 [math. CO] 2012.
[22]A. Heckel, O. Riordan, The hitting time of rainbow connection number two, The electronic journal of combinatorics,19(4)(2012), P37.
[23]J. He, H. Liang, On rainbow-k-connectivity of random graphs, arXiv:1012.1942v 1 [math. CO] 2010.
[24]G.L. Johns, F. Okamoto, P. Zhang, The rainbow connectivities of small cubic graphs, Ars Combin., to appear.
[25]A. kemnitz, I. Schiermeyer, Graphs with rainbow connection number two, Dis-cuss. Math. Graph Theory,31(2)(2011),313-320.
[26]J. Komlos, M. Simonovits, Szemeredi's Regularity Lemma and its application in graph Theory, In:D. Mikl6s, VT. Sos, T. Szonyi, (eds) Combinatorics, paul Erdo is Eighty. Bolyai society mathematical studies, Budapest,2(1996),295-352.
[27]M. Krivelevich, R. Yuster, The rainbow connection of a graph is (at most) recip-rocal to its minimum degree, J. Graph Theory,63(2010),185-191.
[28]H. Li, X. Li, S. Liu, Rainbow connection of graphs with diameter 2, Discrete Math., in press.
[29]X. Li, M. Liu, I. Schiermeyer, Rainbow connection number of dense graphs, arX-iv:1110.5772v1[math. CO]2011.
[30]X. Li, Y. Sun, Rainbow connection number of line graphs, Ars Combin., 100(2011),449-463.
[31]X. Li, Y. Sun, Upper bounds for the rainbow connection numbers of line graphs, Graphs Combin., in press.
[32]X. Li, Y. Sun, Note on the rainbow k-connectivity of regular complete bipartite graphs, Ars Combin.,101(2011),513-518.
[33]X. Li, Y. Sun, Characterization of graphs with large rainbow connection number and rainbow connection numbers of some graph operations, Discrete Math., to appear.
[34]X. Li, Y. Sun, Rainbow connections of graphs-A survey, Graphs Combin., 29(2013),1-38.
[35]X. Li, Y. Sun, Rainbow Connections of Graphs, SpringerBriefs in Math., Springer, New York,2012.
[36]I. Schiermeyer, On minimally rainbow k-connected graphs, Discrete Appl. Math., in press.
[37]I. Schiermeyer, Rainbow connection in graphs with minimum degree three. I-WOCA 2009, LNCS,5874(2009),432-437.
[38]I. Schiermeyer, Bounds for the rainbow connection number of graphs, Discuss. Math. Graph Theory,31(2011),387-395.
[39]I. Schiermeyer, Rainbow connection and minimum degree, Discrete Appl. Math., to appear.
[40]E. Szemeredi, Regular partitions of graphs, In.Proc. colloque inter. CNRS 260. CNRS, Paris,399-401.
[2]N. Alon, R. Duke, H. Lefmann, V. Rodl, R. Yuster, The algorithmic aspects of the Regularity lemma, J. Algorithms,16(1994),80-109.
[3]N. Alon, J.H. Spencer, The Probabilistic Method,3rd ed, Wiley, New York,2008.
[4]P. Ananth, M. Nasre, New hardness results in rainbow connectivity, arX-iv:1104.2074v1[cs.CC]2011.
[5]M. Basavaraju, L.S. Chandran, D. Rajendraprasad, A. Ramaswamy, Rainbow connection number and radius, Graphs Combin., in press.
[6]J.A. Bondy, U.S.R. Murty, Graph Theory, GTM244, Springer, Berlin(2008).
[7]B. Bollobas, A. Thomason, Threshold functions, Combinatorica,7(1986),35-38.
[8]Y. Caro, A. Lev, Y. Roditty, Z. Tuza, R. Yuster, On rainbow connection, Electron. J. Combin.,15(2008), R57.
[9]S. Chakraborty, E. Fischer, A. Matsliah, Yuster, Hardness and algorithms for rain-bow connection, J. Combin. Optimization,21(2011),330-347.
[10]L.S. Chandran, A. Das, D. Rajendraprasad, N.M. Varma, Rainbow connection number and connected dominating sets, J. Graph Theory,71(2012),206-218.
[11]L.S. Chandran, X. Li, S. Liu, R. Mathew, D. Rajendraprasad, Rainbow connection number and connectivity, Electron. J. Combin.,19(2012), P20.
[12]G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang, Rainbow connection in graph-s, Math. Bohem.,133(2008),85-98.
[13]G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang, The rainbow connectivity of
a graph, Networks,54(2)(2009),75-81.
[14]G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang, On the rainbow connectivity of cages, Congr. Numer.184(2)(2007),209-222.
[15]L. Chen, X. Li, M. Liu, Nordhaus-Gaddum-type theorem for the rainbow vertex-connection number of a graph, Util. Math.86(2011),335-340.
[16]X. Chen, X. Li, A solution to a conjecture on the rainbow connection number, Ars Combin.104(2012),193-196.
[17]J. Dong, X. Li, Upper bound involving parameter σ2(G) for the rainbow connec-tion, accepted by Acta Math. Appl. Sin.(English edition).
[18]J. Dong, X. Li, Rainbow connection numbers and the minimum degree sum of a graph, Science in China Series A, Mathematics,43 (2013),7-14(in Chinese).
[19]J. Dong, X. Li, Rainbow connection numbers, bridges and radius, Graphs Com-bin., in press, doi:10.1007/s00373-012-1218-3.
[20]J. Ekstein, P. Holub, T. Kaiser, M. Koch, S.M. Camacho, Z. Ryjacek, I. Schier-meyer, The rainbow connection number of 2-connected graphs, Discrete Math., in press.
[21]A. Frieze, C.E. Tsourakakis, Rainbow connectivity of sparse random graphs, arX-iv:1201.4603v2 [math. CO] 2012.
[22]A. Heckel, O. Riordan, The hitting time of rainbow connection number two, The electronic journal of combinatorics,19(4)(2012), P37.
[23]J. He, H. Liang, On rainbow-k-connectivity of random graphs, arXiv:1012.1942v 1 [math. CO] 2010.
[24]G.L. Johns, F. Okamoto, P. Zhang, The rainbow connectivities of small cubic graphs, Ars Combin., to appear.
[25]A. kemnitz, I. Schiermeyer, Graphs with rainbow connection number two, Dis-cuss. Math. Graph Theory,31(2)(2011),313-320.
[26]J. Komlos, M. Simonovits, Szemeredi's Regularity Lemma and its application in graph Theory, In:D. Mikl6s, VT. Sos, T. Szonyi, (eds) Combinatorics, paul Erdo is Eighty. Bolyai society mathematical studies, Budapest,2(1996),295-352.
[27]M. Krivelevich, R. Yuster, The rainbow connection of a graph is (at most) recip-rocal to its minimum degree, J. Graph Theory,63(2010),185-191.
[28]H. Li, X. Li, S. Liu, Rainbow connection of graphs with diameter 2, Discrete Math., in press.
[29]X. Li, M. Liu, I. Schiermeyer, Rainbow connection number of dense graphs, arX-iv:1110.5772v1[math. CO]2011.
[30]X. Li, Y. Sun, Rainbow connection number of line graphs, Ars Combin., 100(2011),449-463.
[31]X. Li, Y. Sun, Upper bounds for the rainbow connection numbers of line graphs, Graphs Combin., in press.
[32]X. Li, Y. Sun, Note on the rainbow k-connectivity of regular complete bipartite graphs, Ars Combin.,101(2011),513-518.
[33]X. Li, Y. Sun, Characterization of graphs with large rainbow connection number and rainbow connection numbers of some graph operations, Discrete Math., to appear.
[34]X. Li, Y. Sun, Rainbow connections of graphs-A survey, Graphs Combin., 29(2013),1-38.
[35]X. Li, Y. Sun, Rainbow Connections of Graphs, SpringerBriefs in Math., Springer, New York,2012.
[36]I. Schiermeyer, On minimally rainbow k-connected graphs, Discrete Appl. Math., in press.
[37]I. Schiermeyer, Rainbow connection in graphs with minimum degree three. I-WOCA 2009, LNCS,5874(2009),432-437.
[38]I. Schiermeyer, Bounds for the rainbow connection number of graphs, Discuss. Math. Graph Theory,31(2011),387-395.
[39]I. Schiermeyer, Rainbow connection and minimum degree, Discrete Appl. Math., to appear.
[40]E. Szemeredi, Regular partitions of graphs, In.Proc. colloque inter. CNRS 260. CNRS, Paris,399-401.