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
[v1] 28 Jan 2011
Unique-IP document downloads: 164 times
Add your own feedback and questions here: