1. Home
  2. Vol 6, No 2 (2024)
  3. Rahmadani

Rainbow Connection Number of Octopus Iteration Graphs

Desi Rahmadani, Adinda Evelyn Giyanatta, Dina Pratiwi, Mahmuddin Yunus, Vita Kusumasari

Abstract


The rainbow connection number of a graph G denoted by rc(G) is the minimum number of colors used to color the edges in G, such that every pair of vertices is connected by a path with all different colors. In 2008, Chartrand et al. first introduced the concept of rainbow connection numbers. They introduced it as an edge coloring on a graph that refers to the path of each pair of vertices. An octopus graph, with m legs denoted by Om, is a graph constructed from a fan graph Fm and a star graph Sm. The graphs studied in this article are two classes of octopus iteration graphs, namely the octopus chain graph and the octopus ladder graph. The octopus chain graph, denoted by O2(n) is a graph constructed from n copies of O2 and connecting one leg of the i-th copy to the (i+1)-th copy, for every I = 1,2,..., n-1. The octopus ladder graph, denoted by O2'(n) is a graph constructed from graph O2(n) by connecting one of vertex of degree two of the i-th copy to the (i+1)-th copy. In this research, we determine the rainbow connection number of the octopus chain graphs O2(n) and the octopus ladder graphs O2'(n). We obtain that rc(O2(n))=3n, for n >= 1 and rc(O2'(n))=3n-1,  for n >= 2.

Keywords: classes of octopus iteration graphs; octopus chain graph; octopus ladder graph; rainbow connection number.

 

Abstrak

Bilangan terhubung pelangi pada graf G dinotasikan dengan rc(G)  merupakan jumlah warna minimum yang digunakan untuk mewarnai sisi pada G, sehingga setiap pasang titik dihubungkan oleh suatu lintasan dengan warna yang berbeda semua. Pada tahun 2008, Chartrand dkk. pertama kali memperkenalkan konsep bilangan terhubung pelangi. Chartrand dkk. memperkenalkannya sebagai pewarnaan sisi pada graf yang mengacu pada lintasan setiap pasang titiknya. Graf gurita dengan m kaki dinotasikan denganOm  adalah graf yang dikonstruksi dari graf kipas Fm  dan graf bintang Sm. Graf yang dikaji dalam artikel ini merupakan dua kelas graf iterasi gurita, yaitu graf rantai gurita dan graf tangga gurita. Graf rantai gurita yang dinotasikan dengan O2(n) adalah graf yang dikonstruksi dari n copy graf Om dan menghubungkan satu kaki salinan ke-i ke salinan ke-i+1, untuk setiap i = 1,2,...,n. Graf tangga gurita yang dinotasikan dengan O2'(n)  adalah graf yang dibangun dari graf O2(n) dengan menghubungkan salah satu titik berderajat dua salinan dari graph ke-i ke salinan ke-i+1. Pada penelitian ini, ditentukan bilangan terhubung pelangi pada graf rantai gurita O2(n) dan graf tangga gurita O2'(n). Kami memperoleh bahwa rc(O2(n))=3n untuk n>=1 dan rc(O2'(n))=3n-1, untuk n>=2.

Kata Kunci: kelas graf iterasi gurita; graf rantai gurita; graf tangga gurita; bilangan terhubung pelangi.

 

2020MSC: 05C15, 05C40.


Keywords


classes of octopus iteration graphs; octopus chain graph; octopus ladder graph; rainbow connection number.

References


R. Diestel, Graph Theory: Electronic Edition 2005. New York: Springer International Publishing, 2005.

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, doi: 10.21136/MB.2008.133947.

J. D. O. Bastos, H. Lefmann, A. Oertel, C. Hoppen, and D. R. Schmidt, “Maximum number of r-edge-colorings such that all copies of Kk are rainbow,” Procedia Computer Science, vol. 195, pp. 419–426, 2021, doi: 10.1016/j.procs.2021.11.051.

S. Fujita, B. Ning, C. Xu, and S. Zhang, “On sufficient conditions for rainbow cycles in edge-colored graphs,” Discrete Mathematics, vol. 342, no. 7, pp. 1956–1965, Jul. 2019, doi: 10.1016/j.disc.2019.03.012.

K. N. Humolungo, S. Ismail, I. K. Hasan, and N. I. Yahya, “Bilangan Terhubung Pelangi Pada Graf Hasil Operasi Korona Graf Antiprisma (APm) dan Graf Lengkap (K4),” Jurnal Matematika UNAND, vol. 11, no. 2, p. 112, Apr. 2022, doi: 10.25077/jmua.11.2.112-123.2022.

A. D. M. Syah and I. K. Budayasa, “Bilangan Keterhubungan Pelangi Graf ‘Snark’ Bunga,” MU, vol. 9, no. 1, pp. 89–95, Jan. 2021, doi: 10.26740/mathunesa.v9n1.p89-95.

D. A. N. Fadlilah and I. K. Budayasa, “Bilangan Keterhubungan Pelangi Kuat Graf Kupu-Kupu, Benes, dan Torus,” MU, vol. 10, no. 1, pp. 208–217, Apr. 2022, doi: 10.26740/mathunesa.v10n1.p208-217.

I. S. Kumala, “Bilangan Terhubung Pelangi Graf Bunga (W_m,K_n ) dan Graf Lemon (Le_n),” jmpm j. mat. dan pendidik. mat., vol. 4, no. 1, pp. 39–48, Mar. 2019, doi: 10.26594/jmpm.v4i1.1618.

Y. J. Fransiskus Fran Helmi, “Bilangan Terhubung Pelangi Pada Graf Planter dan Graf Gurita,” Bimaster, vol. 8, no. 1, Jan. 2019, doi: 10.26418/bbimst.v8i1.30508.

I. Lihawa, S. Ismail, I. K. Hasan, L. Yahya, S. K. Nasib, and N. I. Yahya, “Bilangan Terhubung Titik Pelangi pada Graf Hasil Operasi Korona Graf Prisma (P_(m,2)) dan Graf Lintasan (P_3),” Jambura J. Math, vol. 4, no. 1, pp. 145–151, Jan. 2022, doi: 10.34312/jjom.v4i1.11826.

A. Y. Saputri, T. Nusantara, and D. Rahmadani, “Rainbow connection number on amalgamation of tadpole graphs and amalgamation of sun graphs,” AIP Conf. Proc. 2639, 040005 (Proceeding of The 2nd International Conference on Mathematics and its Applications 2021). 2022, doi: https://doi.org/10.1063/5.0119684.

A. Y. Saputri, H. Susanto, and D. Rahmadani, “Rainbow connection and strong rainbow connection number on the corona product of sandat graphs,”AIP Conf. Proc. 3049, 020030 (Proceeding of The 3rd International Conference on Mathematics and its Applications 2022), 2024, doi: https://doi.org/10.1063/5.0194363.

A. E. Samuel and S. Kalaivani, “Prime Labeling For Some Octopus Related Graphs,” IOSR Journal of Mathematics (IOSR-JM), vol.12, Issue 6 Ver. III (Nov. - Dec.2016), pp.57-64, 2016, doi: 10.9790/5728-1206035764.

Sy. Syafrizal, G. H. Medika, and L. Yulianti, The rainbow connection of fan and sun, Appl. Math. Sci., vol.7, no. 64, pp. 3155–3160, 2013.

K. Q. Fredlina, A.N.M. Salman, I. gede P.K. Julihara, K.T. Werthi, and N.L.P.N.S.P. Astawa, J, “Rainbow Coloring of Three New Graph Classes,” Phys. Conf. Ser. 1783, 2021, doi: 10.1088/1742-6596/1783/1/012033.

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, doi: https://doi.org/10.1016/j.procs.2015.12.093.

D. Parmar, P. V. Shah, and B. Suthar, Rainbow connection number of triangular snake graph, JETIR, vol.6, issue. 3, pp. 339–343, 2019.


Full Text: PDF

DOI: 10.15408/inprime.v6i2.41414

Refbacks

  • There are currently no refbacks.