The minimum size of graphs with given rainbow index

Abstract

The concept of $k$-rainbow index $r{x}_k(G)$ of a connected graph $G$, introduced by Chartrand, Okamoto and Zhang, is a natural generalization of the rainbow connection number. Let $t(n,k,\ell )$ denote the minimum size of a connected graph $G$ of order $n$ with $r{x}_k(G)\le \ell$, where $2\le \ell \le n-1$ and $2\le k\le n$. In this paper, we obtain some exact values and some upper bounds for $t(n,k,\ell )$.

11pages