On The Rainbow Connection Number Of2-(Edge-)Connected Graphs

As a strengthening of the classical connectivity concept in graphs, the concept of rainbow connection of a graph was first proposed by Chartrand, Johns, McKeon and Zhang in2008. Let G be a nontrivial connected graph with an edge-coloring c: E(G)â†'{1,2,…,k}, k∈N, where adjacent edges may be colored the same. A path in G is rainbow if the colors of its edges are distinct. An edge-colored graph G is said to be rainbow connected if every pair of vertices is connected by at least one rainbow path. An edge-coloring which makes G rainbow connected is called a rainbow coloring (or rainbow edge-coloring). 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. Clearly, every rainbow connected graph is a connected graph and every connected graph has a rainbow coloring by coloring all edges with distinct colors.Besides its theoretical interest as being a natural combinatorial concept, rainbow connection also finds applications in networking problems. Actually, these concepts come from the secure communication of information between agencies of governmen-t. Suppose we wish to route messages in a cellular network such that each link on one route between two vertices is assigned with a distinct channel (e.g. a distinct fre-quency). Clearly, we want to minimize the number of distinct channels that we use in our work. Then the smallest number is exactly the rainbow connection number of the underlying graph.A well-known result of Menger shows that a graph is k-connected if and only if any two distinct vertices of it are connected by k internally disjoint paths. Hence, there is a natural generalization of rainbow connection as follows. Let G be an l-connected graph with an edge-coloring. For any integer k with1≤k≤l, the graph G is rainbow k-connected if any two distinct vertices of G are connected by k internally disjoint rainbow paths. The rainbow k-connection number rck(G) of G is defined to be the minimum integer t such that there exists an edge-coloring of G with t colors which makes G rainbow k-connected. By definition, rck(G) is a generalization of rc(G) and rc1(G)=rc(G). Menger’s Theorem also shows that a graph is k-edge-connected if and only if any two distinct vertices of it are connected by k edge disjoint paths. Let G be an l-edge-connected graph with an edge-coloring. For any k∈N with1≤k≤l, if for any two distinct vertices u, v of G there exist at least k edge disjoint rainbow paths in G from u to v, we say that G is rainbow k-edge-connected and the edge-coloring of G is called a rainbow k-edge-connection coloring. The rainbow k-edge-connection number of G, denoted by rc’k(G), is the minimum integer j such that there exists an edge-coloring of G with j colors which makes G rainbow k-edge-connected.Krivelevich and Yuster first proposed the concept of rainbow vertex-connection. A path in a vertex-colored graph G is a rainbow path if its internal vertices have distinct colors. A vertex-colored graph G is called rainbow vertex-connected if for any two vertices of G, there exists at least one rainbow path between them and we say such a vertex-coloring as a rainbow vertex-coloring of G. The rainbow vertex-connection number of a connected graph G, denoted by rvc(G), is the minimum number of colors required to color the vertices of G to make it rainbow vertex-connected. Note that a rainbow path in an edge-colored graph is different from the one in a vertex-colored graph.This thesis includes five chapters. In Chapter1, we introduce the definition and background of rainbow connection and give the basic notation and terminology used in this thesis. We also present an overview of results on rainbow connection including the main results of this thesis.In Chapter2, we will discuss some preliminary knowledge and some simple prop-erties about rainbow connection which will be used in the proofs of the results in this thesis.In Chapter3, we first introduce a new concept of incomplete rainbow coloring, and using it show that every2-connected graph G of order n has a rainbow edge-coloring with at most[n/2] colors, i.e., rc(G)≤[n/2]. Then we characterize some Hamilto-nian graphs G of order n satisfying that rc(G)=[n/2].Finally, we obtain that for a connected graph G of order n with cut vertices, rc(G)≤(n+r-1)/2, where r is the number of blocks of G with even orders, and based on it, prove a tight upper bound for the rainbow connection number of a2-edge-connected graph G of order n(n≥3), i.e.,Fujita, Liu and Magnant [35,37] proposed a problem:What is the minimum con-stant α>0such that for every2-connected graph G on n vertices, we have rc2(G)≤αn? In Chapter4, we prove that the minimum constant α=1and rc2(G)=n if and only if G is a cycle of order n, which solves the problem of Fujita et. al. As a gener-alization, we first give the definition of rainbow k-edge-connection number of a graph G, denoted by rc’k(G). We also show that if G is a2-edge-connected graph of order n, then rc’2(G)≤n with equality if and only if G is a cycle of order n.In Chapter5, we first determine the rainbow vertex-connection number of a cy-cle Cn of order n(n≥3), and then, based on it, prove that for any2-connected graph G of order n, rvc(G)≤rvc(Cn), giving a tight upper bound for the rainbow vertex-connection number of2-connected graphs. As a consequence, we show that for a con-nected graph G with a block decomposition B1,B2,…,Bk and t cut vertices, rvc(G)≤rvc(B1)+rvc(B2)+…+rvc(Bk)+t. We also characterize the Hamiltonian graphs of order n with rainbow vertex-connection number[n/2].