Name
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 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. In this work we study the rainbow connection of the random r-regular graph G = G(n, r) of order n, 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(log n), which is best possible up to a hidden constant. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1137/140998433 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
rainbow connection,random regular graphs,edge coloring | Discrete mathematics,Edge coloring,Binary logarithm,Graph,Combinatorics,Colored,Vertex (geometry),Infinity,Connectivity,Rainbow,Mathematics | Journal |
Volume | Issue | ISSN |
29 | 4 | 0895-4801 |
Citations | PageRank | References |
5 | 0.50 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrzej Dudek | 1 | 114 | 23.10 |
| Alan M. Frieze | 2 | 4837 | 787.00 |
| Charalampos E. Tsourakakis | 3 | 1003 | 51.15 |