A Solution to a Conjecture on Two Rainbow Connection Numbers of a Graph

Xiaolin Chern1, Xueliang Li1
1Center for Combinatorics and LPMC-TJKLC Nankai University, Tianjin 300071, P.R. China

Abstract

For a graph \(G\), Chartrand et al. defined the rainbow connection number \(rc(G)\) and the strong rainbow connection number \(src(G)\) in “G. Chartrand, G.L. John, K.A. McKeon, P. Zhang, Rainbow connection in graphs, Mathematica Bohemica, \(133(1)(2008) 85-98\)”. They raised the following conjecture: for two given positive integers \(a\) and \(b\), there exists a connected graph \(G\) such that \(rc(G) = a\) and \(src(G) = b\) if and only if \(a = b \in \{1,2\}\) or \(3 \leq a \leq b”\). In this short note, we will show that the conjecture is true.