Some Topics On Rainbow (Vertex-) Connection Numbers Of Graphs

Let G be a nontrivial connected graph with an edge-coloring, where adjacent edges may be colored the same. A path of G is a rainbow path if no two edges of the path are colored the same. The graph G is rainbow connected if for every two vertices u and v, there is a rainbow path connecting u and v. The minimum number of colors for which there is an edge-coloring of G such that G is rainbow connected is called the rainbow connection number, denoted by rc(G).The concept of rainbow connection number was introduced by Chartrand et al. in2008. It is a natural and interesting way to strengthen the connectiv-ity requirement, since if a graph is rainbow connected, it is obvious connected. Rainbow connection number of graphs also has its application in practice. It comes from the secure communication of information between agencies of govern-ment. For national security, when we assign information transfer paths between agencies, we require a large enough number of passwords that is prohibitive to intruders, such that one or more paths between every pair of agencies have no password repeated. On the other hand, we hope that the number of passwords is as small as possible. When we model the information communication network by a graph, and use the colors to represent the passwords, then this minimum number of passwords is what we call rainbow connection number.As an analogous concept of rainbow connection number, Krivelevich and Yuster proposed the concept of rainbow vertex-connection number. Let G be a nontrivial connected graph with a vertex-coloring. A path of G is a rainbow vertex-connected path if the internal vertices of the path have distinct colors. The graph G is rainbow vertex-connected if for every two vertices u and v, there is a rainbow vertex-connected path connecting u and v. The minimum number of colors for which there is a vertex-coloring of G such that G is rainbow vertex-connected is called the rainbow vertex-connection number, denoted by rvc(G). This thesis consists of three chapters. In Chapter1, we introduce the defini-tions and the background of rainbow (vertex-) connection numbers of graphs, and list the notation and terminology which are used in this thesis. We also give an overview of results on rainbow (vertex-) connection numbers of graphs, including the main results of this thesis.A Nordhaus-Gaddum type bound is a lower or upper bound on the sum or product of the values of a parameter for a graph G and its complement G. In1956, Nordhaus and Gaddum established these bounds for the chromatic number. Since then, relations of this type of other graph parameters have been considered by many graph theorists, and the bound of this type is called Nordhaus-Gaddum type bound. In Chapter2, we study the Nordhaus-Gaddum type bounds for the rainbow connection number and the rainbow vertex-connection number. First, we consider the Nordhaus-Gaddum type bound for the rainbow connection number. We show that rc(G)+rc(G)≤n+2by induction on n, where n is the number of vertices of G, and we also show that the upper bound is best possible for all n≥4. Since rc(G)≥2for a noncomplete graph G, we have rc(G)+rc(G)≥4, and the bound is sharp for all n≥8. For4≤n≤7, we obtain a better lower bound. That is, for n=4,5, rc(G)+rc(G)>6, and for n=6,7, rc(G)+rc(G)≥5, all these bounds are best possible. Similarly, we get the Nordhaus-Gaddum type bound for the rainbow vertex-connection number. We prove that2≤rvc(G)+rvc(G)≤n-1for all n>5, and these bounds are best possible.In Chapter3, we focus on the complexity of rainbow vertex-connection num-ber of graphs. Caro et al. conjectured that computing rc(G) is an NP-hard problem, as well as that even deciding whether a graph G has rc(G)=2is NP-complete. This conjecture has been proved by Chakraborty et al. They also proved that determining whether a given edge-coloring of a graph G makes it rainbow connected is NP-complete. Motivated by their work, we consider the complexity of determining the rainbow vertex-connection number of a graph. We prove that given a graph G, deciding whether rvc(G)=2is NP-complete. Thus, computing rvc(G) is NP-hard. And the following problem is NP-complete:giv-en a vertex-colored graph G, check whether the given coloring makes G rainbow vertex-connected. In the paper of Chakraborty, they only show that deciding whether a graph G has rc(G)=2is NP-complete, but what about deciding whether a graph G has rc(G)≤k for a fixed integer k,k＜3. They conjectured that it is NP-complete. P. Ananth and M. Nasre then proved the conjecture. They showed that for every k≥3, deciding whether rc(G)<k is NP-hard. Sim-ilarly, we consider the complexity of deciding whether a graph G has rvc(G)≤k for a fixed integer k, k≥3. We show that for every integer k≥2, to decide whether rvc(G)<k is NP-hard. Moreover, for any fixed integer k≥2, the problem belongs to NP-class, and therefore it is NP-complete.