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

r c (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 = f r a c l o g n + o m n

where

o m = o m (n) o i n f t y

and

o m = o (l o g n)

and of random

r

-regular graphs where

r g e q 3

is a fixed integer. Specifically, we prove that the rainbow connectivity

r c (G)

of

G = G (n, p)

satisfies

r c (G) s i m m a x s e t Z_{1}, d i a m e t e r (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

d i a m

whp. Finally, we prove that the rainbow connectivity

r c (G)

of the random

r

-regular graph

G = G (n, r)

satisfies

r c (G) = O (l o g^{2} n)

whp.

Recommendations

Cited in

(13)

This page was built for publication: Rainbow connectivity of sparse random graphs