The hitting time of rainbow connection number two

Author: 

Heckel, A
Riordan, O

Publication Date: 

6 December 2012

Journal: 

ELECTRONIC JOURNAL OF COMBINATORICS

Last Updated: 

2019-08-14T22:07:50.853+01:00

Issue: 

4

Volume: 

19

page: 

P37-P37

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) ≥ diam(G). We will show that for the Erdo{double acute}s-Rényi 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: 

Submitted to ORA: 

Not Submitted

Publication Type: 

Journal Article