2012/01/22 by Frieze, Alan, Tsourakakis, Charalampos E.
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1201.4603
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=(log n+\om)/(n) where \om=\om(n)→∞ and \om=o(logn) and of random r-regular graphs where r ≥ 3 is a fixed integer. Specifically, we prove that the rainbow connectivity rc(G) of G=G(n,p) satisfies rc(G) ∼ max\setZ1,diameter(G) with high probability (\whp). Here Z1 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(log2n) \whp.