More on 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 et al., is a natural generalization of the rainbow connection number of a graph. Liu introduced a parameter t(n, k, ℓ) to investigate the problems of the minimum size of a connected graph with given order and k-rainbow index at most ℓ and obtained some exact values and upper bounds for t(n, k, ℓ). In this paper, we obtain some exact values of t(n, k, ℓ) for large ℓ and better upper bounds of t(n, k, ℓ) for small ℓ and k = 3.

Keywords

• steiner distance
• rainbow s-tree
• k-rainbow index
• 05c05
• 05c15
• 05c75