Geodesic
The Vertex-Rainbow Index of A Graph
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 669-681.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: vertex-coloring, connectivity, vertex-rainbow S-tree, vertex- rainbow index, Nordhaus-Gaddum type 
@article{DMGT_2016_36_3_a11,
     author = {Mao, Yaping},
     title = {The {Vertex-Rainbow} {Index} of {A} {Graph}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {669--681},
     publisher = {mathdoc},
     volume = {36},
     number = {3},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a11/}
}
TY  - JOUR
AU  - Mao, Yaping
TI  - The Vertex-Rainbow Index of A Graph
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 669
EP  - 681
VL  - 36
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a11/
LA  - en
ID  - DMGT_2016_36_3_a11
ER  - 
%0 Journal Article
%A Mao, Yaping
%T The Vertex-Rainbow Index of A Graph
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 669-681
%V 36
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a11/
%G en
%F DMGT_2016_36_3_a11
Mao, Yaping. The Vertex-Rainbow Index of A Graph. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 669-681. http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a11/

[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

[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

[4] Q. Cai, X. Li and J. Song, The (k, ℓ)-rainbow index of random graphs, Bull. Malays. Math. Sci. Soc. 39 (2016) 765-771.

[5] Y. Caro, A. Lev, Y. Roditty, Z. Tuza and R. Yuster, On rainbow connection, Elec- tron. J. Combin. 15 (2008) #R57.

[6] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85-98.

[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

[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 .

[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

[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

[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.

[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

[13] X. Cheng and D. Du, Steiner Trees in Industry (Kluwer Academic Publisher, Dor- drecht, 2001).

[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

[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

[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

[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

[19] X. Li and Y. Shi, On the rainbow vertex-connection, Discuss. Math. Graph Theory 33 (2013) 307-313. doi:10.7151/dmgt.1664

[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

[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

[23] E.A. Nordhaus and J.W. Gaddum, On complementary graphs, Amer.Math.Monthly 63 (1956) 175-177.

[24] I. Schiermeyer, On minimally rainbow k-connected graphs, Discrete Appl. Math. 161 (2013) 702-705. doi:10.1016/j.dam.2011.05.001