Journal article

The hitting time of rainbow connection number two

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 \$...

Publication status:
Published

Authors

Journal:
Electronic J. Combinatorics 19 (2012), Issue 4, P37
Volume:
19
Issue:
4
Pages:
P37-P37
Publication date:
2012-09-13
EISSN:
1077-8926
ISSN:
1077-8926
Source identifiers:
350702
Language:
English
Keywords:
Pubs id:
pubs:350702
UUID:
uuid:47e9162c-ac86-4361-982e-73468337bc29
Local pid:
pubs:350702
Deposit date:
2013-11-17