The Rainbow Connection Of The Special Graph

As the origin of the graph theory, the famous Konigsberg Bridge Problem, promotes the development of the graph theory. The coloring of a graph has always been a hot issue in the field of graph theory research. It not only has theoretical value, but also has the important practical significance. Moreover, the connectivity is one important character of a graph, so rainbow connection number which combines the coloring and connectivity emerged. The rainbow connection was introduced by Chartrand, Johns, McKeon and Zhang in 2008, which has been applied to the fields of cryptography, security of network etc.Let G be a nontrivial connectedgraph on which an edge-coloring c:E(G)â†'{1,2,...,n}, n∈N, is defined, where adjacentedges may be colored in the same way. A path is rainbow if no two edges of it are colored the same. An edge-coloring graph G is rainbow connected if any two vertices are connected by a rainbowpath. An edge-coloring under which G is rainbow connected is called a rainbow coloring. Thus, we define the rainbow connection number of a connected graph G, denoted by rc(G), as the smallest number of colors that are needed in order to make G rainbow connected.Later, Krivelevich and Yusterput forward the rainbow vertex connection number. Similar to the rainbow connection number, a vertex-colored graph G is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. A vertex-coloring under which G is rainbow vertex-connected is called a rainbow vertex-coloring. The rainbow vertex-connection number of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected.This paper mainly studies the rainbow connectivity. The main results are as follows:(1)The background, basic concepts and conclusion of the graphs are introduced.(2)We calculate the (strong) rainbow connection numbers of the thorn of the complete, the thorn of the circle and the windmill.(3)We also calculate the corona graph with rigorous mathematical induction.(4)We calculate the rainbow vertex-connection number of 3-connected graph.