| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420044 | Discrete Applied Mathematics | 2013 | 4 Pages |
An edge-coloured graph GG is rainbow connected if any two vertices are connected by a path whose edges have distinct colours. A graph GG is called rainbow kk-connected if there is an edge colouring of GG with kk colours such that GG is rainbow connected.In this paper we will study rainbow kk-connected graphs with a minimum number of edges. For an integer n≥3n≥3 and 1≤k≤n−11≤k≤n−1 let t(n,k)t(n,k) denote the minimum size of a rainbow kk-connected graph GG of order nn. We will compute exact values and upper bounds for t(n,k)t(n,k).
► In this paper, edge colourings of graphs are considered. ► A path between two vertices whose edges are coloured distinctly is a rainbow path. ►GG is called rainbow connected if all pairs of vertices have a rainbow path. ►GG is called rainbow kk-connected if the edges of GG are coloured with kk colours. ► We are studying rainbow kk-connected graphs with a minimum number of edges.
