The Vertex-Rainbow Index of A Graph

• Autorzy: Yaping Mao
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

vertex-coloring; connectivity; vertex-rainbow S-tree; vertex- rainbow index; Nordhaus-Gaddum type

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 3
• Strony: 669-681

Daty

wydano

2016-08-01

otrzymano

2014-09-11

poprawiono

2015-10-13

zaakceptowano

2015-10-13

online

2016-07-06

Twórcy

autor

Yaping Mao

• Department of Mathematics Qinghai Normal University Qinghai 810008, China

Bibliografia

• [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]
• [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]
• [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[Crossref]
• [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[Crossref]
• [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]
• [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[WoS]
• [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[Crossref][WoS]
• [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]
• [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]
• [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]
• [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]
• [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]
• [23] E.A. Nordhaus and J.W. Gaddum, On complementary graphs, Amer.Math.Monthly 63 (1956) 175-177. [Crossref]
• [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]

Identyfikatory

DOI

10.7151/dmgt.1887