The minimum size of graphs with given rainbow index

Abstract

The concept of k-rainbow index rxk(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, l) denote the minimum size of a connected graph G of order n with rxk(G) ≥ l, where 2 ≥ l ≥ n - 1 and 2 ≥ k ≥ n. In this paper, we obtain some exact values and some upper bounds for t(n, k,l). © 2018 Utilitas Mathematica Publishing Inc. All rights reserved.