Authors:
Y. Zhao
Title:
More on the minimum size of graphs with given rainbow index
Source:
Discussiones Mathematicae Graph Theory
Received 05.06.2017, Revised 15.01.2018, Accepted 03.03.2018, doi: 10.7151/dmgt.2131

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

Links:
PDF