The Strong 3-Rainbow Index of Graphs Containing Three Cycles
Abstract
The concept of a strong k-rainbow index is a generalization of a strong rainbow connection number, which has an interesting application in security systems in a communication network. Let G be an edge-colored connected graph of order n, where adjacent edges may be colored the same. A rainbow tree in G is a tree whose edges have distinct colors. For an integer k with 2≤k≤n, the strong k-rainbow index srx_k (G) of G is the minimum number of colors needed to color all edges of G so that every k vertices of G are connected by a rainbow tree of minimum size. We focus on k=3. It is clear that srx_3 (G)≤‖G‖, where the upper bound is sharp since the srx_3 of a tree equals its size. Hence, we are interested in studying how the srx_3 of a tree changes if we add some edges connecting two nonadjacent vertices in the tree. This paper is focused on graphs containing three cycles. We first determine a sharp upper bound of the srx_3 of graphs containing exactly three edge-disjoint cycles. We also determine the exact values of srx_3 of theta graph θ(a_1,a_2,a_3) for certain values of a_1, a_2, and a_3.
Keywords: cycle; rainbow coloring; rainbow Steiner tree; theta graph; tree.
Abstrak
Konsep indeks pelangi-k kuat merupakan perumuman dari bilangan terhubung pelangi kuat yang memiliki aplikasi menarik dalam sistem keamanan jaringan komunikasi. Misalkan G adalah suatu graf terhubung berorde n yang memiliki suatu pewarnaan sisi, dimana dua sisi bertetangga boleh memiliki warna yang sama. Pohon pelangi di G adalah pohon yang setiap sisinya memiliki warna berbeda. Untuk suatu bilangan bulat k dengan 2≤k≤n, indeks pelangi-k kuat srx_k (G) graf G adalah banyak warna minimum yang dibutuhkan untuk mewarnai semua sisi di G sehingga setiap k titik di G dihubungkan oleh suatu pohon pelangi berukuran minimum. Kami fokus pada k=3. Jelas bahwa srx_3 (G)≤‖G‖, dimana batas atas ini merupakan batas ketat karena srx_3 pohon sama dengan ukurannya. Karena itu, kami tertarik untuk mempelajari bagaimana srx_3 pohon berubah jika ditambahkan beberapa sisi yang menghubungkan dua titik tidak bertetangga di pohon tersebut. Artikel ini difokuskan pada graf yang memuat tiga siklus. Pertama, kami menentukan batas atas ketat srx_3 graf yang memuat tepat tiga siklus saling lepas sisi. Kami juga menentukan nilai eksak srx_3 graf theta θ(a_1,a_2,a_3 ) untuk beberapa nilai a_1, a_2, dan a_3 tertentu.
Kata Kunci: siklus; pewarnaan pelangi; pohon Steiner pelangi; graf theta; pohon.
2020MSC: 05C05, 05C15, 05C38, 05C40.
Keywords
References
R. Diestel, Graph Theory (5th Edition). Springer Berlin Heidelberg, 2017.
G. Chartrand, G. L. Johns, K. A. McKeon, and P. Zhang, “Rainbow connection in graphs,” Mathematica Bohemica, vol. 133, no. 1, pp. 85–98, 2008.
Y. Caro, A. Lev, Y. Roditty, Z. Tuza, and R. Yuster, “On Rainbow Connection,” The Electronic Journal of Combinatorics, vol. 15, R57, 2008.
S. Chakraborty, E. Fischer, A. Matsliah, and R. Yuster, “Hardness and algorithms for rainbow connection,” Journal of Combinatorial Optimization, vol. 21, no. 3, pp. 330–347, 2009.
D. Fitriani and A. N. M. Salman, “Rainbow connection number of amalgamation of some graphs,” AKCE International Journal of Graphs and Combinatorics, vol. 13, no. 1, pp. 90–99, 2016.
D. Fitriani, A. N. M. Salman, and Z. Y. Awanis, “Rainbow connection number of comb product of graphs,” Electronic Journal of Graph Theory and Applications, vol. 10, no. 2, pp. 461–473, 2022.
I. S. Kumala and A. N. M. Salman, “The rainbow connection number of a flower (C_m,K_n ) graph and a flower (C_3,F_n ) graph”, Procedia Computer Science, vol. 74, pp. 168–172, 2015.
S. Nabila and A. N. M. Salman, “The rainbow connection number of origami graphs and pizza graphs”, Procedia Computer Science, vol. 74, pp. 162–167, 2015.
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, vol. 74, pp. 143–150, 2015.
B. H. Susanti, A. N. M. Salman, and R. Simanjuntak, “The rainbow connection number of some subdivided roof graphs”, AIP Conference Proceedings, vol. 1707, 020021, 2016.
Susilawati and A. N. M. Salman, “Rainbow connection number of rocket graphs”, AIP Conference Proceedings, vol. 1677, 030012, 2015.
X. Li, Y. Shi, and Y. Sun, “Rainbow connections of graphs: a survey,” Graphs and Combinatorics, vol. 29, no. 1, pp. 1–38, 2013.
X. Li and Y. Sun, “An updated survey on rainbow connections of graphs - a dynamic survey,” Theory and Applications of Graphs, vol. 0, no. 1, article 3, 2017.
Z. Y. Awanis and A. N. M. Salman, “The strong 3-rainbow index of some certain graphs and its amalgamation,” Opuscula Mathematica, vol. 42, no. 4, pp. 527–547, 2022.
G. Chartrand, F. Okamoto, and P. Zhang, “Rainbow trees in graphs and generalized connectivity,” Networks, vol. 55, no. 4, pp. 360–367, 2010.
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, vol. 44, pp. 446–462, 2020.
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, vol. 28, pp. 865–875, 2020.
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,” Electronic Journal of Graph Theory and Applications, vol. 10, no. 1, pp. 33–50, 2022.
A. N. M. Salman, Z. Y. Awanis, and S. W. Saputro, “Graphs with strong 3-rainbow index equals 2,” Journal of Physics: Conference Series, vol. 2157, 012011, 2022.
DOI: 10.15408/inprime.v5i1.29133
Refbacks
- There are currently no refbacks.
.
