Solutions to conjectures on the $(k,\ell )$-rainbow index of complete graphs

Abstract

The $(k,\ell )$-rainbow index $r{x}_{k,\ell }(G)$ of a graph $G$ was introduced by Chartrand et. al. For the complete graph $K_n$ of order $n\ge 6$, they showed that $r{x}_{3,\ell }(K_n)=3$ for $\ell =1,2$. Furthermore, they conjectured that for every positive integer $\ell$, there exists a positive integer $N$ such that $r{x}_{3,\ell }(K_n)=3$ for every integer $n\ge N$. More generally, they conjectured that for every pair of positive integers $k$ and $\ell$ with $k\ge 3$, there exists a positive integer $N$ such that $r{x}_{k,\ell }(K_n)=k$ for every integer $n\ge N$. This paper is to give solutions to these conjectures.

9 pages