Author
Heckel, A
Riordan, O
Journal title
Electronic J. Combinatorics 19 (2012), Issue 4, P37
Last updated
2023-12-19T21:15:28.227+00:00
Abstract
In a graph $G$ with a given edge colouring, a rainbow path is a path all of
whose edges have distinct colours. The minimum number of colours required to
colour the edges of $G$ so that every pair of vertices is joined by at least
one rainbow path is called the rainbow connection number $rc(G)$ of the graph
$G$. For any graph $G$, $rc(G) \ge diam(G)$. We will show that for the
Erd\H{o}s-R\'enyi random graph $G(n,p)$ close to the diameter 2 threshold, with
high probability if $diam(G)=2$ then $rc(G)=2$. In fact, further strengthening
this result, we will show that in the random graph process, with high
probability the hitting times of diameter 2 and of rainbow connection number 2
coincide.
Symplectic ID
350702
Download URL
http://arxiv.org/abs/1209.2981v1
Favourite
Off
Publication type
Journal Article
Publication date
13 Sep 2012
Please contact us with feedback and comments about this page. Created on 15 Sep 2012 - 20:42.