The Rainbow Connection Number of Snail Graphs and Jellyfish Graphs
Main Article Content
Abstract
The rainbow connection number is a topic in graph theory that studies the minimum number of colors required on the edges of a graph such that every pair of vertices is connected by a path with distinct edge colors. This study aims to determine the rainbow connection number of snail graphs and jellyfish graphs. The method used is a theoretical approach through structural analysis of graphs and the construction of minimum edge-coloring patterns that satisfy the rainbow connected property. The results show that the rainbow connection number of the snail graph Sl_n is rc(Sl_n)=4 for n=1,2, rc(Sl_n)=5 for n=3,4, and rc(Sl_n)=6 for n≥5. Meanwhile, for the jellyfish graph J_n, it is obtained that rc(J_n)=2n+1. These results indicate that the structure of a graph significantly influences the rainbow connection number. Although the diameter of the jellyfish graph is constant, the structural complexity causes the rainbow connection number to increase linearly with respect to n. This study is expected to contribute to the development of research on rainbow connection in special graphs.
Article Details
References
[1] G. Chartrand, G. L. Johns, K. A. McKeon, and P. Zhang, “Rainbow connection in graphs,” Math. Bohem., vol. 133, no. 1, pp. 85–98, 2008.
[2] R. Diestel, Graph Theory, 5th ed. Berlin: Springer, 2017.
[3] D. B. West, Introduction to Graph Theory, 3rd ed. Pearson, 2021.
[4] X. Li and Y. Sun, Rainbow Connections of Graphs. New York: Springer, 2012. doi: 10.1007/978-1-4614-3118-0.
[5] S. Sy, G. H. Medika, and L. Yulianti, “The Rainbow Connection of Fan and Sun,” Appl. Math. Sci., vol. 7, no. 64, pp. 3155–3160, 2013.
[6] M. A. Shulhany and A. N. M. Salman, “Bilangan Terhubung Pelangi Graf Berlian,” Pros. Semin. Nas. Mat. dan Pendidik. Mat. UMS, no. 1, pp. 916–923, 2015.
[7] I. S. Kumala, “Bilangan Terhubung Pelangi pada Graf Bunga dan Graf lemon,” Mat. dan Pendidik. Mat., vol. 4, no. 1, pp. 39–48, 2019.
[8] C. A. P. Noor, L. Yahya, S. K. Nasib, and N. I. Yahya, “Bilangan Terhubung Pelangi Pada Graf Salju (Sn_m),” J. Fundam. Math. Appl., vol. 4, no. 1, pp. 29–44, 2021, doi: 10.14710/jfma.v4i1.9035.
[9] N. Lakisa, N. Nurwan, S. K. Nasib, and N. I. Yahya, “Bilangan Terhubung Pelangi pada Graf Ferris Wheel (Fw_n),” JMPM J. Mat. dan Pendidik. Mat., vol. 7, no. 1, pp. 66–80, 2022, doi: 10.26594/jmpm.v7i1.2337.
[10] D. N. Asmara, “Bilangan Rainbow Connection Dan Strong Rainbow Connection Pada Graf Jahangir,” J. Mat. Unand, vol. VII, no. 1, pp. 52–58, 2018.
[11] G. H. Medika, Z. B. Tomi, and E. R. Wulan, “Bilangan rainbow connection pada graf buku,” KUBIK J. Publ. Ilm. Mat., vol. 9, no. 1, pp. 87–97, 2024.
[12] A. Maulani, “Rainbow Connection and Strong Rainbow Connection of Corona Graphs,” Indones. J. Comb., vol. 4, no. 2, pp. 45–54, 2020.
[13] T. D. Doan and I. Schiermeyer, “Proper Rainbow Connection Number of Graphs,” Discret. Appl. Math., vol. 255, pp. 56–63, 2019, doi: 10.1016/j.dam.2018.07.030.
[14] A. F. Akadji, “Rainbow Vertex Connection Number and Strong Rainbow Vertex Connection Number of Graphs,” Desimal J. Mat., vol. 4, no. 2, pp. 159–166, 2021.
[15] G. H. Medika, S. Sy, Muhafzan, and Zulfaneti, “Rainbow Connection Numbers In Graphs : A Comprehensive Study Bilangan Rainbow Connection Pada Graf : Kajian Komprehensif,” Math Educ. J., vol. 10, no. 1, pp. 44–59, 2026.
[16] G. H. Medika and S. Sy, “The Rainbow Connection Number of Snail Graphs,” BiCED Proceeding, vol. 3, no. 1, pp. 1--6, 2025.
[17] J. A. Bondy and U. S. R. Murty, Graph Theory. London: Springer, 2008. doi: 10.1007/978-1-84628-970-5.
[18] K. Akbar and K. A. Sugeng, “Pelabelan graceful pada graf siput dan graf ubur-ubur,” in Prosiding KNM XX, Universitas Pattimura, 2021, pp. 143–148. doi: 10.30598/PattimuraSci.2021.KNMXX.143-148.