PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 3 | 669-681
Tytuł artykułu

The Vertex-Rainbow Index of A Graph

Autorzy
Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
36
Numer
3
Strony
669-681
Opis fizyczny
Daty
wydano
2016-08-01
otrzymano
2014-09-11
poprawiono
2015-10-13
zaakceptowano
2015-10-13
online
2016-07-06
Twórcy
autor
  • Department of Mathematics Qinghai Normal University Qinghai 810008, China, maoyaping@ymail.com
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]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1887
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.