Rainbow Connection Number of Octopus Iteration Graphs - Rahmadani, Desi; Giyanatta, Adinda Evelyn; Pratiwi, Dina; Yunus, Mahmuddin; Kusumasari, Vita (InPrime: Indonesian Journal of Pure and Applied Mathematics, 2024)
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. AbstrakBilangan 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.