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 rx_{k}(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: |