Rainbow Connection of Random Regular Graphs
Andrzej Dudek
Alan Frieze
Charalampos E. Tsourakakis
10.1184/R1/6479219.v1
https://kilthub.cmu.edu/articles/journal_contribution/Rainbow_Connection_of_Random_Regular_Graphs/6479219
<p>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 connection 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. <br>In this work we study the rainbow connection of the random r-regular graph G=G(n,r) of ordern, where r≥4 is a constant. We prove that with probability tending to one as n goes to infinity the rainbow connection of G satisfies rc(G)=O(logn), which is best possible up to a hidden constant.</p>
2013-11-11 00:00:00
Mathematical Sciences