Upper Bounds On The Rainbow Connection Number Of Graphs

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.