| dc.description.abstract | Let G = (V; E) be a simple, nontrivial, nite, connected and undirected
graph. Let c be a coloring c : E(G) ! f1; 2; : : : ; sg; s 2 N. A path of edge colored
graph is said to be a rainbow path if no two edges on the path have the same color. An
edge colored graph G is said to be a rainbow connected graph if there exists a rainbow
u v path for every two vertices u and v of G. The rainbow connection number of a
graph G, denoted by rc(G), is the smallest number of k colors required to edge color
the graph such that the graph is rainbow connected. Furthermore, for an l-connected
graph G and an integer k with 1 k l, the rainbow k-connection number rc
(G)
of G is de ned to be the minimum number of colors required to color the edges of G
such that every two distinct vertices of G are connected by at least k internally disjoint
rainbow paths. In this paper, we determine the exact values of rainbow connection
number of some special graphs and obtain a sharp lower bound. | en_US |
