Upper bounds of the strong 3-rainbow index of corona product graphs
Abstract
A tree in an edge-colored connected graph G of order n, where adjacent edges may be colored the same, is a rainbow tree if no two of its edges have the same color. Let k be an integer with 2 ≤ k ≤ n. An edge-coloring of G is called a strong k-rainbow coloring of G if for every S ⊆ V(G) with |S| = k, there exists a rainbow tree of minimum size connecting S. The minimum number of colors that are needed such that G admits a strong k-rainbow coloring is called the strong k-rainbow index of G, denoted by srxk(G). In this paper, we study the srx3 of corona product between two connected graphs G and H, denoted by G ⊙ H. We first provide an algorithm to define a strong 3-rainbow coloring of G ⊙ H. Hence, we obtain a sharp upper bound for srx3(G ⊙ H). We also characterize graphs H with srx3(Tn ⊙ H) equals the upper bound.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2026.14.2.1
References
Z.Y. Awanis and A.N.M. Salman, The 3-rainbow index of amalgamation of some graphs with diameter 2, IOP Conference Series: Journal of Physics 1127 (2019), 012058. doi: 10.1088/1742-6596/1127/1/012058
Z.Y. Awanis and A.N.M. Salman, The strong 3-rainbow index of some certain graphs and its amalgamation, Opuscula Math. 42 (2) (2022), 527–547. doi: 10.7494/OpMath.2022.42.4.527
Z.Y. Awanis, A. Salman, S.W. Saputro, M. Bača, and A. Semaničová-Feňovčíková, The strong 3-rainbow index of edge-amalgamation of some graphs, Turkish J. Math. 44 (2020), 446–462. doi: 10.3906/mat-1911-49
Z.Y. Awanis, A.N.M. Salman, and S.W. Saputro, The strong 3-rainbow index of comb product of a tree and a connected graph, Journal of Information Processing 28 (2020), 865–875. doi: 10.2197/ipsjjip.28.865
Z.Y. Awanis, A.N.M. Salman, and S.W. Saputro, The strong 3-rainbow index of edge-comb product of a path and a connected graph, Electron. J. Graph Theory Appl. 10 (1) (2022), 33–50. doi: 10.5614/ejgta.2022.10.1.3
Z.Y. Awanis, A.N.M. Salman, and S.W. Saputro, The strong 3-rainbow index of graphs containing some cycles, J. Indones. Math. Soc. 32(1) (2026), 1–17. doi: 10.22342/jims.v32i1.1513
Q. Cai, X. Li, and Y. Zhao, Note on the upper bound of the rainbow index of a graph, Discrete Appl. Math. 209 (2016), 68–74. doi: 10.1016/j.dam.2015.10.019
Y. Caro, A. Lev, Y. Roditty, Z. Tuza, and R. Yuster, On rainbow connection, Electron. J. Combin. 15 (2008), R57. doi: 10.37236/781
S. Chakraborty, E. Fischer, A. Matsliah, and R. Yuster, Hardness and algorithms for rainbow connection, J. Comb. Optim. 21 (2011), 330–347.
G. Chartrand, G.L. Johns, K.A. McKeon, and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133(1) (2008), 85–98. doi: 10.21136/MB.2008.133947
G. Chartrand, F. Okamoto, and P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks 55 (2010), 360–367. doi: 10.1002/net.20339
L. Chen, X. Li, K. Yang, and Y. Zhao, The 3-rainbow index of a graph, Discuss. Math. Graph Theory 35(1) (2015), 81–94. doi: 10.7151/dmgt.1780
R. Diestel, Graph Theory 5ed. (Springer, 2017).
D. Fitriani and A.N.M. Salman, Rainbow connection number of amalgamation of some graphs, AKCE Int. J. Graphs Comb. 13 (2016), 90–99. doi: 10.1016/j.akcej.2016.03.004
D. Fitriani, A.N.M. Salman, and Z.Y. Awanis, Rainbow connection number of comb product of graphs, Electron. J. Graph Theory Appl. 10 (2) (2022), 461–473. doi: 10.5614/ejgta.2022.10.2.9
D. Kartika and A.N.M. Salman, The 3-rainbow index of some graphs that constructed by joining a graph with a trivial graph, IOP Conference Series: Journal of Physics 1127 (2019), 012060. doi: 10.1088/1742-6596/1127/1/012060
I.S. Kumala and A.N.M. Salman, The rainbow connection number of a flower (Cm, Kn) graph and a flower (C3, Fn) graph, Procedia Computer Science 74 (2015), 168–172. doi: 10.1016/j.procs.2015.12.094
S. Li, X. Li, and Y. Shi, Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs, Appl. Math. Comput. 258 (2015), 155–161. doi: 10.1016/j.amc.2015.02.015
X. Li and Y. Sun, An updated survey on rainbow connections of graphs - a dynamic survey, Theory Appl. Graphs 0(1) (2017), Article 3. doi: 10.20429/tag.2017.000103
X. Li, Y. Shi, and Y. Sun, Rainbow connections of graphs: a survey, Graphs Combin. 29 (2013), 1–38.
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
T. Liu and Y. Hu, The 3-rainbow index of graph operations, WSEAS Transactions on Mathematics 13 (2014), 161–170.
T. Liu and Y. Hu, Some upper bounds for 3-rainbow index of graphs, J. Combin. Math. Combin. Comput. 97 (2016), 217–225.
S. Nabila and A.N.M. Salman, The rainbow connection number of origami graphs and pizza graphs, Procedia Computer Science 74 (2015), 162–167. doi: 10.1016/j.procs.2015.12.093
D. Resty and 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. doi: 10.1016/j.procs.2015.12.090
A.N.M. Salman, Z.Y. Awanis, and S.W. Saputro, Graphs with strong 3-rainbow index equals 2, IOP Conference Series: Journal of Physics 2157 (2022), 012011. doi: 10.1088/1742-6596/2157/1/012011
D.N.S. Simamora and A.N.M. Salman, The rainbow (vertex) connection number of pencil graphs, Procedia Computer Science 74 (2015), 138–142. doi: 10.1016/j.procs.2015.12.089
R.F. Umbara, A.N.M. Salman, and P.E. Putri, On the inverse graph of a finite group and its rainbow connection number, Electron. J. Graph Theory Appl. 11(1) (2023), 135–147.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.