Displaying similar documents to “Edge-disjoint 1-factors in powers of connected graphs”

Rainbow Connection In Sparse Graphs

Arnfried Kemnitz, Jakub Przybyło, Ingo Schiermeyer, Mariusz Woźniak (2013)

Discussiones Mathematicae Graph Theory

Similarity:

An edge-coloured connected graph G = (V,E) is called rainbow-connected if each pair of distinct vertices of G is connected by a path whose edges have distinct colours. The rainbow connection number of G, denoted by rc(G), is the minimum number of colours such that G is rainbow-connected. In this paper we prove that rc(G) ≤ k if |V (G)| = n and for all integers n and k with n − 6 ≤ k ≤ n − 3. We also show that this bound is tight.