Rainbow Connectivity of Sparse Random Graphs

Abstract

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 connectivity 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. In this work we study the rainbow connectivity of binomial random graphs at the connectivity threshold $p=\frac{\log n+\om}{n}$ where $\om=\om(n)\to\infty$ and ${\om}=o(\log{n})$ and of random $r$-regular graphs where $r\ge 3$ is a fixed integer. Specifically, we prove that the rainbow connectivity $rc(G)$ of $G=G(n,p)$ satisfies $rc(G)\sim \max \{Z_1,diameter(G)\}$ with high probability (\whp). Here $Z_1$ is the number of vertices in $G$ whose degree equals 1 and the diameter of $G$ is asymptotically equal to $\diam$ \whp. Finally, we prove that the rainbow connectivity $rc(G)$ of the random $r$-regular graph $G=G(n,r)$ satisfies $rc(G)=O({\log }^{2}n)$ \whp.

17 pages, 4 figures Accepted at APPROX-RANDOM'12