Opuscula Math. 42, no. 4 (2022), 527-547
https://doi.org/10.7494/OpMath.2022.42.4.527
Opuscula Mathematica
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.
- 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
- 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
- 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
- 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
- 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
- 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
- R. Diestel, Graph Theory, 4th ed., Springer, Heidelberg, 2010.
- A.B. Ericksen, A matter of security, Graduating Engineer and Computer Careers (2007), 24-28.
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Communicated by Ingo Schiermeyer.
- Received: 2021-07-21.
- Revised: 2022-02-06.
- Accepted: 2022-04-19.
- Published online: 2022-06-30.
