Affordable Access

The rainbow connection number of 2-connected graphs

Authors
Journal
Discrete Mathematics
0012-365X
Publisher
Elsevier
Publication Date
Volume
313
Issue
19
Identifiers
DOI: 10.1016/j.disc.2012.04.022
Keywords
  • 05C15
  • Rainbow Connection Number
  • Graph
  • Connectivity

Abstract

Abstract The rainbow connection number of a graph G is the least number of colours in a (not necessarily proper) edge-colouring of G such that every two vertices are joined by a path which contains no colour twice. Improving a result of Caro et al., we prove that the rainbow connection number of every 2-connected graph with n vertices is at most ⌈n/2⌉. The bound is optimal.

There are no comments yet on this publication. Be the first to share your thoughts.