Combinatorics and Graph Theory

1101 Submissions

[1] viXra:1101.0095 [pdf] submitted on 28 Jan 2011

Sharp Concentration of the Rainbow Connection of Random Graphs

Authors: Yilun Shang
Comments: 5 pages

An edge-colored graph G is rainbow edge-connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection 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. Similarly, a vertex-colored graph G is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection 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. We prove that both rc(G) and rvc(G) have sharp concentration in classical random graph model G(n, p).
Category: Combinatorics and Graph Theory