The k-rainbow index rxk(G) of a connected graph G was introduced by Chartrand, Okamoto and Zhang in 2010. As a natural counterpart of the k-rainbow index, we introduce the concept of k-vertex-rainbow index rvxk(G) in this paper. In this paper, sharp upper and lower bounds of rvxk(G) are given for a connected graph G of order n, that is, 0 ≤ rvxk(G) ≤ n − 2. We obtain Nordhaus-Gaddum results for 3-vertex-rainbow index of a graph G of order n, and show that rvx3(G) + rvx3(Ḡ) = 4 for n = 4 and 2 ≤ rvx3(G) + rvx3(Ḡ) ≤ n − 1 for n ≥ 5. Let t(n, k, ℓ) denote the minimal size of a connected graph G of order n with rvxk(G) ≤ ℓ, where 2 ≤ ℓ ≤ n − 2 and 2 ≤ k ≤ n. Upper and lower bounds on t(n, k, ℓ) are also obtained.
@article{bwmeta1.element.doi-10_7151_dmgt_1887,
author = {Yaping Mao},
title = {The Vertex-Rainbow Index of A Graph},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {669-681},
zbl = {1339.05056},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1887}
}
Yaping Mao. The Vertex-Rainbow Index of A Graph. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 669-681. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1887/
[1] M. Aouchiche and P. Hansen, A survey of Nordhaus-Gaddum type relations, Discrete Appl. Math. 161 (2013) 466-546. doi:10.1016/j.dam.2011.12.018[Crossref][WoS] | Zbl 1259.05083
[2] J.A. Bondy and U.S.R. Murty, Graph Theory (Graduate Texts in Mathematics 244, Springer-Verlag, London, 2008).
[3] Q. Cai, X. Li and J. Song, Solutions to conjectures on the (k, ℓ)-rainbow index of complete graphs, Networks 62 (2013) 220-224. doi:10.1002/net.21513[Crossref]
[4] Q. Cai, X. Li and J. Song, The (k, ℓ)-rainbow index of random graphs, Bull. Malays. Math. Sci. Soc. 39 (2016) 765-771.[Crossref][WoS] | Zbl 1333.05073
[5] Y. Caro, A. Lev, Y. Roditty, Z. Tuza and R. Yuster, On rainbow connection, Elec- tron. J. Combin. 15 (2008) #R57. | Zbl 1181.05037
[6] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85-98. | Zbl 1199.05106
[7] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, The rainbow connectivity of a graph, Networks 54 (2009) 75-81. doi:10.1002/net.20296[Crossref] | Zbl 1205.05124
[8] G. Chartrand, O.R. Oellermann, S. Tian and H.B. Zou, Steiner distance in graphs, Časopis pro pěstování matematiky 114 (1989) 399-410 . | Zbl 0688.05040
[9] G. Chartrand, F. Okamoto and P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks 55 (2010) 360-367. doi:10.1002/net.20340[Crossref] | Zbl 1205.05085
[10] L. Chen, X. Li and H. Lian, Nordhaus-Gaddum-type theorem for rainbow connection number of graphs, Graphs Combin. 29 (2013) 1235-1247. doi:10.1007/s00373-012-1183-x[Crossref][WoS] | Zbl 1272.05044
[11] L. Chen, X. Li and M. Liu, Nordhaus-Gaddum-type theorem for the rainbow vertex connection number of a graph, Util. Math. 86 (2011) 335-340. | Zbl 1264.05048
[12] L. Chen, X. Li, K. Yang and Y. Zhao, The 3-rainbow index of a graph, Discuss. Math. Graph Theory 35 (2015) 81-94. doi:10.7151/dmgt.1780[WoS]
[13] X. Cheng and D. Du, Steiner Trees in Industry (Kluwer Academic Publisher, Dor- drecht, 2001). | Zbl 1179.90277
[14] D. Du and X. Hu, Steiner Tree Problems in Computer Communication Networks (World Scientific, River Edge, 2008).
[15] M. Krivelevich and R. Yuster, The rainbow connection of a graph is (at most) re- ciprocal to its minimum degree, J. Graph Theory 63 (2010) 185-191. doi:10.1002/jgt.20418[Crossref][WoS] | Zbl 1193.05079
[16] H. Li, X. Li, Y. Sun and Y. Zhao, Note on minimally d-rainbow connected graphs, Graphs Combin. 30 (2014) 949-955. doi:10.1007/s00373-013-1309-9[WoS][Crossref] | Zbl 1298.05125
[17] X. Li, I. Schiermeyer, K. Yang and Y. Zhao, Graphs with 3-rainbow index n−1 and n − 2, Discuss. Math. Graph Theory 35 (2015) 105-120. doi:10.7151/dmgt.1783[Crossref] | Zbl 1307.05051
[18] X. Li, I. Schiermeyer, K. Yang and Y. Zhao, Graphs with 4-rainbow index 3 and n − 1, Discuss. Math. Graph Theory 35 (2015) 387-398. doi:10.7151/dmgt.1794[Crossref] | Zbl 1311.05032
[19] X. Li and Y. Shi, On the rainbow vertex-connection, Discuss. Math. Graph Theory 33 (2013) 307-313. doi:10.7151/dmgt.1664[Crossref][WoS]
[20] X. Li, Y. Shi and Y. Sun, Rainbow connections of graphs: A survey, Graphs Combin. 29 (2013) 1-38. doi:10.1007/s00373-012-1243-2[Crossref][WoS] | Zbl 1258.05058
[21] X. Li and Y. Sun, Rainbow Connections of Graphs (SpringerBriefs in Math., Springer, New York, 2012).
[22] Y. Mao and Y. Shi, The complexity of determining the vertex-rainbow index of graphs, Discrete Math. Algorithms Appl. 7(4) (2015) 1550047. doi:10.1142/s1793830915500470[Crossref][WoS] | Zbl 1331.05064
[23] E.A. Nordhaus and J.W. Gaddum, On complementary graphs, Amer.Math.Monthly 63 (1956) 175-177. [Crossref] | Zbl 0070.18503
[24] I. Schiermeyer, On minimally rainbow k-connected graphs, Discrete Appl. Math. 161 (2013) 702-705. doi:10.1016/j.dam.2011.05.001[WoS][Crossref] | Zbl 1259.05102