The strong 3-rainbow index of edge-comb product of a path and a connected graph

Zata Yumni Awanis, A.N.M. Salman, Suhadi Wido Saputro

Abstract


Let G be a connected and edge-colored graph of order n, where adjacent edges may be colored the same. A tree in G is a rainbow tree if all of its edges have distinct colors. Let k be an integer with 2 ≤ k ≤ n. The minimum number of colors needed in an edge coloring of G such that there exists a rainbow tree connecting S with minimum size for every k-subset S of V(G) is called the strong k-rainbow index of G, denoted by srxk(G). In this paper, we study the srx3 of edge-comb product of a path and a connected graph, denoted by Pno⊳eH. It is clearly that |E(Pno⊳eH)| is the trivial upper bound for srx3(Pno⊳eH). Therefore, in this paper, we first characterize connected graphs H with srx3(Pno⊳eH)=|E(Pno⊳eH)|, then provide a sharp upper bound for srx3(Pno⊳eH) where srx3(Pno⊳eH)≠|E(Pno⊳eH)|. We also provide the exact value of srx3(Pno⊳eH) for some connected graphs H.

Keywords


edge-comb product; rainbow coloring; rainbow Steiner tree; strong 3-rainbow index

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2022.10.1.3

References

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 Journal of Mathematics 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 and A.N.M. Salman, The strong 3-rainbow index of some certain graphs and its amalgamation, submitted.

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

M. Bača, A.N.M. Salman, R. Simanjuntak, and B.H. Susanti, Rainbow 2-connectivity of edge-comb product of a cycle and a Hamiltonian graph, Proceedings Mathematical Sciences 130 (2020), 1–12. doi:10.1007/s12044-019-0549-x

Y. Caro, A. Lev, Y. Roditty, Z. Tuza, and R. Yuster, On rainbow connection, The Electronic Journal of Combinatorics 15 (2008), R57. doi:10.37236/781

S. Chakraborty, E. Fischer, A. Matsliah, and R. Yuster, Hardness and algorithms for rainbow connectivity, Journal of Combinatorial Optimization 21 (2011), 330–347.

G. Chartrand, G.L. Johns, K.A. McKeon, and P. Zhang, Rainbow connection in graphs, Mathematica Bohemica 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, Discussiones Mathematicae 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 International Journal of Graphs and Combinatorics 13 (2016), 90–99. doi:10.1016/j.akcej.2016.03.004

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

X. Li, Y. Shi, and Y. Sun, Rainbow connections of graphs: a survey, Graphs and Combinatorics 29(1) (2013), 1–38.

X. Li and Y. Sun, An updated survey on rainbow connections of graphs - a dynamic survey, Theory and Applications of Graphs 0(1) (2017), Article 3. doi:10.20429/tag.2017.000103

T. Liu and Y. Hu, The 3-rainbow index of graph operations, WSEAS Transactions on Mathematics 13 (2014), 161–170.

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

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


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats