The Vertex-Rainbow Index of A Graph

Yaping Mao

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 3, page 669-681
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Yaping Mao. "The Vertex-Rainbow Index of A Graph." Discussiones Mathematicae Graph Theory 36.3 (2016): 669-681. <http://eudml.org/doc/285645>.

@article{YapingMao2016,
abstract = {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.},
author = {Yaping Mao},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {vertex-coloring; connectivity; vertex-rainbow S-tree; vertex- rainbow index; Nordhaus-Gaddum type; vertex coloring; vertex-rainbow -tree; vertex-rainbow index},
language = {eng},
number = {3},
pages = {669-681},
title = {The Vertex-Rainbow Index of A Graph},
url = {http://eudml.org/doc/285645},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Yaping Mao
TI - The Vertex-Rainbow Index of A Graph
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 3
SP - 669
EP - 681
AB - 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.
LA - eng
KW - vertex-coloring; connectivity; vertex-rainbow S-tree; vertex- rainbow index; Nordhaus-Gaddum type; vertex coloring; vertex-rainbow -tree; vertex-rainbow index
UR - http://eudml.org/doc/285645
ER -

References

top
  1. [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] Zbl1259.05083
  2. [2] J.A. Bondy and U.S.R. Murty, Graph Theory (Graduate Texts in Mathematics 244, Springer-Verlag, London, 2008). 
  3. [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. [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] Zbl1333.05073
  5. [5] Y. Caro, A. Lev, Y. Roditty, Z. Tuza and R. Yuster, On rainbow connection, Elec- tron. J. Combin. 15 (2008) #R57. Zbl1181.05037
  6. [6] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85-98. Zbl1199.05106
  7. [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] Zbl1205.05124
  8. [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 . Zbl0688.05040
  9. [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] Zbl1205.05085
  10. [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] Zbl1272.05044
  11. [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. Zbl1264.05048
  12. [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. [13] X. Cheng and D. Du, Steiner Trees in Industry (Kluwer Academic Publisher, Dor- drecht, 2001). Zbl1179.90277
  14. [14] D. Du and X. Hu, Steiner Tree Problems in Computer Communication Networks (World Scientific, River Edge, 2008). 
  15. [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] Zbl1193.05079
  16. [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] Zbl1298.05125
  17. [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] Zbl1307.05051
  18. [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] Zbl1311.05032
  19. [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. [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] Zbl1258.05058
  21. [21] X. Li and Y. Sun, Rainbow Connections of Graphs (SpringerBriefs in Math., Springer, New York, 2012). 
  22. [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] Zbl1331.05064
  23. [23] E.A. Nordhaus and J.W. Gaddum, On complementary graphs, Amer.Math.Monthly 63 (1956) 175-177. [Crossref] Zbl0070.18503
  24. [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] Zbl1259.05102

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.