Combinatorics and Graph Theory

   

Sharp Concentration of the Rainbow Connection of Random Graphs

Authors: Yilun Shang

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).

Comments: 5 pages

Download: PDF

Submission history

[v1] 28 Jan 2011

Unique-IP document downloads: 164 times

Add your own feedback and questions here:

comments powered by Disqus