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

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\le a\le b”$. In this short note, we will show that the conjecture is true.