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

• Autorzy: Awanis Zata Yumni , Salman A.N.M.

Identyfikatory

DOI

10.7494/OpMath.2022.42.4.527

• Języki publikacji: EN

Abstrakty

EN

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 ≤ k ≤ n. The strong k-rainbow index of G, denoted by srxk(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.

Słowa kluczowe

EN

amalgamation; rainbow coloring; rainbow Steiner tree; strong k-rainbow index

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2022
• Tom: Vol. 42, no. 4
• Strony: 527--547
• Opis fizyczny: Bibliogr. 16 poz.

Twórcy

autor

Awanis Zata Yumni

• Institut Teknologi Bandung, Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Jalan Ganesa 10, Bandung 40132, Indonesia

• https://orcid.org/0000-0001-8927-6043

autor

Salman A.N.M.

• Institut Teknologi Bandung, Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Jalan Ganesa 10, Bandung 40132, Indonesia

Bibliografia

• [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.
• [2] Y. Caro, A. Lev, Y. Roditty, Z. Tuza, R. Yuster, On rainbow connection, Electron. J. Combin. 15 (2008), R57.
• [3] S. Chakraborty, E. Fischer, A. Matsliah, R. Yuster, Hardness and algorithms for rainbow connectivity, J. Comb. Optim. 21 (2011), 330–347.
• [4] G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008), 85–98.
• [5] G. Chartrand, F. Okamoto, P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks 55 (2010), 360–367.
• [6] L. Chen, X. Li, K. Yang, Y. Zhao, The 3-rainbow index of a graph, Discuss. Math. Graph Theory 35 (2015), 81–94.
• [7] R. Diestel, Graph Theory, 4th ed., Springer, Heidelberg, 2010.
• [8] A.B. Ericksen, A matter of security, Graduating Engineer and Computer Careers (2007), 24–28.
• [9] D. Fitriani, A.N.M. Salman, Rainbow connection number of amalgamation of some graphs, AKCE Int. J. Graphs Combin. 13 (2016), 90–99.
• [10] I.S. Kumala, 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.
• [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.
• [12] X. Li, Y. Shi, Y. Sun, Rainbow connections of graphs: a survey, Graphs Combin. 29 (2013), 1–38.
• [13] X. Li, Y. Sun, An updated survey on rainbow connections of graphs – a dynamic survey, Theory Appl. Graphs 0 (2017), Article 3.
• [14] S. Nabila, A.N.M. Salman, The rainbow connection number of origami graphs and pizza graphs, Procedia Computer Science 74 (2015), 162–167.
• [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.
• [16] D.N.S. Simamora, A.N.M. Salman, The rainbow (vertex) connection number of pencil graphs, Procedia Computer Science 74 (2015), 138–142.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).