Opuscula Mathematica
Opuscula Math. 42, no. 4 (2022), 527-547

The strong 3-rainbow index of some certain graphs and its amalgamation

Zata Yumni Awanis
A.N.M. Salman
Abstract. We introduce a strong \(k\)-rainbow index of graphs as modification of well-known \(k\)-rainbow index of graphs. A tree in an edge-colored connected graph \(G\), where adjacent edge may be colored the same, is a rainbow tree if all of its edges have distinct colors. Let \(k\) be an integer with \(2\leq k\leq n\). The strong \(k\)-rainbow index of \(G\), denoted by \(srx_k(G)\), is the minimum number of colors needed in an edge-coloring of \(G\) so that every \(k\) vertices of \(G\) is connected by a rainbow tree with minimum size. We focus on \(k=3\). We determine the strong \(3\)-rainbow index of some certain graphs. We also provide a sharp upper bound for the strong \(3\)-rainbow index of amalgamation of graphs. Additionally, we determine the exact values of the strong \(3\)-rainbow index of amalgamation of some graphs.
Keywords: amalgamation, rainbow coloring, rainbow Steiner tree, strong \(k\)-rainbow index.
Mathematics Subject Classification: 05C05, 05C15, 05C40.
Full text (pdf)
References ▼
  1. [1] Z.Y. Awanis, A.N.M. Salman, The \(3\)-rainbow index of amalgamation of some graphs with diameter \(2\), Journal of Physics: IOP Conference Series 1127 (2019), 012058. https://doi.org/10.1088/1742-6596/1127/1/012058
  2. [2] Y. Caro, A. Lev, Y. Roditty, Z. Tuza, R. Yuster, On rainbow connection, Electron. J. Combin. 15 (2008), R57. https://doi.org/10.37236/781
  3. [3] S. Chakraborty, E. Fischer, A. Matsliah, R. Yuster, Hardness and algorithms for rainbow connectivity, J. Comb. Optim. 21 (2011), 330-347. https://doi.org/10.1007/s10878-009-9250-9
  4. [4] G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008), 85-98. https://doi.org/10.21136/MB.2008.133947
  5. [5] G. Chartrand, F. Okamoto, P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks 55 (2010), 360-367. https://doi.org/10.1002/net.20339
  6. [6] L. Chen, X. Li, K. Yang, Y. Zhao, The \(3\)-rainbow index of a graph, Discuss. Math. Graph Theory 35 (2015), 81-94. https://doi.org/10.7151/dmgt.1780
  7. [7] R. Diestel, Graph Theory, 4th ed., Springer, Heidelberg, 2010.
  8. [8] A.B. Ericksen, A matter of security, Graduating Engineer and Computer Careers (2007), 24-28.
  9. [9] D. Fitriani, A.N.M. Salman, Rainbow connection number of amalgamation of some graphs, AKCE Int. J. Graphs Combin. 13 (2016), 90-99. https://doi.org/10.1016/j.akcej.2016.03.004
  10. [10] I.S. Kumala, A.N.M. Salman, he rainbow connection number of a flower \((C_m,K_n)\) graph and a flower \((C_3,F_n)\) graph, Procedia Computer Science 74 (2015), 168-172. https://doi.org/10.1016/j.procs.2015.12.094
  11. [11] S. Li, X. Li, Y. Shi, Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs, Appl. Math. Comput. 258 (2015), 155-161. https://doi.org/10.1016/j.amc.2015.02.015
  12. [12] X. Li, Y. Shi, Y. Sun, Rainbow connections of graphs: a survey, Graphs Combin. 29 (2013), 1-38. https://doi.org/10.1007/s00373-012-1243-2
  13. [13] X. Li, Y. Sun, An updated survey on rainbow connections of graphs - a dynamic survey, Theory Appl. Graphs 0 (2017), Article 3. https://doi.org/10.20429/tag.2017.000103
  14. [14] S. Nabila, A.N.M. Salman, The rainbow connection number of origami graphs and pizza graphs, Procedia Computer Science 74 (2015), 162-167. https://doi.org/10.1016/j.procs.2015.12.093
  15. [15] D. Resty, A.N.M. Salman, The rainbow connection number of an \(n\)-crossed prism graph and its corona product with a trivial graph, Procedia Computer Science 74 (2015), 143-150. https://doi.org/10.1016/j.procs.2015.12.090
  16. [16] D.N.S. Simamora, A.N.M. Salman, The rainbow (vertex) connection number of pencil graphs, Procedia Computer Science 74 (2015), 138-142. https://doi.org/10.1016/j.procs.2015.12.089
About the authors ▼
Zata Yumni Awanis (corresponding author)
https://orcid.org/0000-0001-8927-6043
Institut Teknologi Bandung, Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Jalan Ganesa 10, Bandung 40132, Indonesia
A.N.M. Salman
Institut Teknologi Bandung, Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Jalan Ganesa 10, Bandung 40132, Indonesia
About the article ▼
Communicated by Ingo Schiermeyer.
Received: 2021-07-21.
Revised: 2022-02-06.
Accepted: 2022-04-19.
Published online: 2022-06-30.
Cite this article as ▼
Zata Yumni Awanis, A.N.M. Salman, The strong 3-rainbow index of some certain graphs and its amalgamation, Opuscula Math. 42, no. 4 (2022), 527-547, https://doi.org/10.7494/OpMath.2022.42.4.527.
Download this article's citation as: