## EULER: Jurnal Ilmiah Matematika, Sains dan Teknologi
Submit: 22 Mei 2022, Diterima: 29 Juni 2022, Online: 30 Juni 2022 Copyright ©2022 by N. I. Yahya, K. A. Mamonto, N. Nurwan, L. Yahya, D. Wungguli, L. O. Nashar Diterbitkan oleh: Jurusan Matematika Universitas Negeri Gorontalo | Under the licence CC BY-NC 4.0
Bilangan Terhubung Titik Pelangi Kuat Graf Octa-Chain ( )

## Abstrak
Graf  Octa-Chain  ( )  adalah  graf  yang  dibentuk  dari  modifikasi  graf  lingkaran dengan menambahkan suatu sisi yang menghubungkan titik-titik tengah di
. Banyaknya warna minimum yang  digunakan  untuk  mewarnai  titik-titik  dalam  sebuah  graf  sehingga  setiap  dua  titik  terdapat lintasan  pelangi  disebut  bilangan  terhubung  titik  pelangi  yang  dinotasikan  dengan rvc(G) . Sedangkan  banyaknya  warna  minimun yang  digunakan  untuk  mewarnai  titik-titik  dalam  sebuah graf  sehingga  setiap  dua  titik  selalu  dihubungkan  dengan  lintasan  pelangi  disebut  bilangan terhubung  titik  pelangi  kuat  dan  dinotasikan  dengan srvc(G) .  Penelitian  ini  bertujuan  untuk menentukan bilangan terhubung titik pelangi (rvc) dan bilangan terhubung titik pelangi kuat (srvc ) pada graf Octa-Chain ( ) . Hasilnya yang diperoleh dari penelitian ini bilangan terhubung titik pelangi ( ) = 2 dan bilangan terhubung titik pelangi kuat dengan ( ) = 2 .
Kata Kunci: Graf Octa-Chain; Bilangan Terhubung Titik Pelangi; Bilangan Terhubung Titik Pelangi Kuat
Abstract
An Octa-Chain graph ( ) is a graph formed by modifying the cycle graph by adding an edge connecting the midpoints in . The minimum number of colors used to color the vertices in a graph so  that  every  two  vertices  have  a  rainbow  path  is  called  the  rainbow  vertex-connected  number denoted by rvc(G). While the minimum number of colors used to color the vertices in a graph so that every two vertices are always connected by a rainbow path is called a strong rainbow vertex connected  number  and  is  denoted  by  srvc(G).  This study  aims  to  determine  the  rainbow  vertex- connected number (rvc) and the strong rainbow-vertex-connected number (srvc) in the Octa-Chain graph ( ). The results obtained from this research are the rainbow vertex-connected number rvc ( )=2m and the strong rainbow-vertex-connected number srvc ( )=2m.
Keywords: Octa-Chain Graph; Rainbow Vertex-Connected Number; Strong Rainbow-Vertex- Connected Number

## 1. Pendahuluan
Teori graf merupakan salah satu cabang dalam ilmu matematika yang mempelajari sifat-sifat yang dimiliki suatu graf. Graf sering digunakan  untuk merepresentasikan objek-objek diskrit pada matematika  dengan  tujuan  membantu  memvisualisasi  suatu  objek  agar  lebih  mudah  dimengerti. Dalam graf, objek direpresentasikan dalam himpunan titik dan himpunan sisi. Masalah dalam teori graf yang pertama kali dikaji adalah masalah di jembatan Konigsberg oleh ilmuwan matematika yang bernama Leonhard Euler pada tahun 1736 [1].
Graf memiliki beberapa bidang kajian yang sering dikaji untuk dijadikan topik dalam penelitian diantaranya pelabelan, matching , dan masalah lintasan terpendek. Suatu pemetaan atau fungsi yang memasangkan  unsur-unsur  graf  baik  titik  ataupun  sisi  dengan  bilangan  positif  disebut  dengan pelabelan  graf  [2].  Jika  domain  dari  pemetaan  tersebut  merupakan  himpunan  titik  maka  disebut
Nisky Imansyah Yahya 1 *, Karina Anselia Mamonto 1 , Nurwan 1 , Lailany Yahya 1 , Djihad Wungguli 1 , La Ode Nashar 2
1 Program Studi Matematika, Universitas Negeri Gorontalo, Bone Bolango 96119, Indonesia
2 Program Studi Statistika, Universitas Negeri Gorontalo, Bone Bolango 96119, Indonesia *Penulis Korespondensi. Email: nisky@ung.ac.id
pelabelan titik ( vertex labeling ), sedangkan jika domain dari pemetaan tersebut merupakan himpunan sisi maka disebut pelabelan sisi ( edge labeling ) dan jika domainnya merupakan gabungan himpunan titik dan sisi maka disebut pelabelan total ( total labeling) [3].
Topik  pelabelan  graf  yang  semakin  berkembang  salah  satunya  adalah  pewarnaan  graf. Pewarnaan graf merupakan pemberian warna secara langsung kepada suatu graf seperti warna merah, kuning, dan hijau. Bisa juga dengan menggunakan bilangan untuk mewakili warna yang digunakan. Pewarnaan  terdiri  atas  pewarnaan  titik  ( vertex  coloring ),  pewarnaan  sisi  ( edge  coloring ),  dan pewarnaan wilayah ( region coloring ) [4].
Salah  satu  konsep  pewarnaan  graf yaitu  pewarnaan  pelangi.  Pewarnaan  pelangi  yang  terkait dengan konsep keterhubungan graf menjadi asal muasal dari bilangan terhubung pelangi. Bilangan terhubung  pelangi  sendiri  pertama  kali  diperkenalkan  oleh  Chartrand et  al. [5]  yang  menjelaskan mengenai bilangan terhubung pelangi sebagai minimum warna yang digunakan untuk mewarnai sisi dalam  graf  sedemikian  sehingga  setiap  dua  titik  terhubung  dengan  lintasan  pelangi.  Kemudian Krivelevich  [6]  mengembangkan  bilangan  terhubung  titik  pelangi  sebagai  minimum  warna  yang digunakan untuk mewarnai titik dalam graf sedemikian sehingga setiap dua titik terhubung dengan lintasan pelangi. Selanjutnya Li [7] mengembangkan bilangan terhubung titik pelangi kuat sebagai minimum warna yang digunakan untuk mewarnai titik dalam graf sedemikian sehingga setiap dua titik selalu terhubung dengan lintasan pelangi. Selain itu beberapa penelitian relevan terkait bilangan terhubung titik pelangi diantaranya adalah bilangan keterhubungan titik pelangi kuat pada graf oleh Afifuddin  dan  Budayasa  [8],  bilangan  terhubung  titik  pelangi  pada  graf  hasil  operasi  korona  graf prisma ( , ) dan graf lintasan ( ) oleh Lihawa et al. [9], the rainbow (vertex) connection number of pencil graphs oleh Simamora dan Salman [10], the rainbow vertex-connection number of star fan graphs oleh Bustan dan Salman [11] , serta rainbow vertex connection number and strong rainbow vertex connection number on slinky graph ( ) yang dibahas oleh Akadji et al. [12].
Pada  penelitian  ini  ditentukan  dan  dibuktikan  bilangan  terhubung  titik  pelangi  pelangi ( rainbow vertex connection ) atau rvc(G) dan bilangan terhubung titik pelangi kuat ( strong rainbow vertex  connection )  atau srvc(G) pada  graf Octa-Chain .  Graf Octa-Chain merupakan  graf  yang dibentuk  dari  modifikasi  dari  graf  lingkaran
dengan  menambahkan  suatu  sisi  yang menghubungkan titik-titik tengah di dimana titik-titiknya akan diwarnai dengan minimum warna- k sehingga menghasilkan lintasan pelangi.

## 2. Metode Penelitian
Pada  penelitian  ini  metode  penelitian  yang  digunakan  adalah  metode  studi  literatur  dimana sumber penelitian menggunakan berupa buku, textbook , dan artikel ilmiah. Tujuan studi literatur ini adalah  untuk  memperoleh  informasi  mengenai  hal-hal  yang  berkaitan  dengan  graf  dan  bilangan terhubung  titik  pelangi  pelangi  serta  bilangan  terhubung  titik  pelangi  kuat  yang  dibutuhkan untuk menyelesaikan penelitian ini.
Dalam  penelitian  ini,  graf  yang  digunakan  adalah  graf  sederhana,  terbatas,  dan  berhingga. Notasi  dan terminologi graf yang digunakan dalam penelitian ini sesuai dengan Diestel [13]. Graf sederhana  yaitu  graf  yang  tidak  memiliki  sisi  rangkap  dan  loop.  Graf  terbatas  artinya  graf  yang digunakan  adalah  graf  yang  himpunan  titik  dan  simbolnya  terbatas  dan  dapat  disimbolkan  misal ( , , , … , ) , sedangkan graf berhingga artinya jumlah titik dari graf yang digunakan berhingga misalkan graf dengan n buah titik. Adapun graf yang digunakan pada penelitian ini adalah graf Octa- Chain ( ).
Untuk memperoleh hasil yang tepat maka diperlukan beberapa langkah penelitian yang perlu dilakukan. Adapun langkah-langkah tersebut disajikan dalam bentuk diagram alir pada Gambar 1.
Gambar 1 . Diagram Alir Penelitian
Adapun penjelasan yang lebih rinci untuk diagram alir diatas  adalah sebagai berikut:
1. Merumuskan masalah yang akan dibahas
2. Mempelajari berbagai referensi baik dari jurnal, buku, textbook, dan artikel ilmiah yang berkaitan dengan  masalah  yang  akan  dibahas.  Dalam  hal  ini  adalah  bilangan  terhubung  titik  pelangi  dan bilangan terhubung titik pelangi kuat.
3. Mendeskripsikan masalah untuk menganalisis permasalahan yang ada untuk memperoleh pola dan teorema  yang  akan  dibuktikan.  Langkah-langkah  yang  dibutuhkan  untuk  menganalisis  adalah sebagai berikut :
a. Menggambar graf Octa-Chain ( ).
b. Mencari pola dari bilangan terhubung titik pelangi ( rainbow vertex connection ) atau rvc(G) dan bilangan terhubung titik pelangi kuat ( strong rainbow vertex connection ) atau srvc(G) melalui gambar graf Octa-Chain sehingga akan didapatkan pola tentang rvc(G) dan srvc(G) terhadap graf Octa-Chain .
c. Membuktikan  teorema  tentang  bilangan  terhubung  titik  pelangi  ( rainbow  vertex  connection ) atau rvc(G) dan bilangan terhubung titik pelangi kuat ( strong rainbow vertex connection ) atau srvc(G ) yang telah diperoleh dari pola sebelumnya.
4. Merumuskan kesimpulan berdasarkan hasil-hasil analisis teorema yang telah dibuktikan.
Sebelum masuk ke pembahasan, berikut diberikan beberapa teori yang dijadikan acuan pada bagian pembahasan.

## 2.1 Bilangan Terhubung Titik Pelangi
Bilangan terhubung titik pelangi pertama kali diperkenalkan oleh Krivelevich dan Yuster [6] dan memperoleh hasil yang dinyatakan pada Lemma 1.
Lemma  1 .  Graf  berwarna  titik adalah  titik  terhubung  pelangi  jika  terdapat  dua  titik  yang dihubungkan oleh lintasan dengan titik yang memiliki warna berbeda. Titik terhubung pelangi dari graf terhubung   dilambangkan dengan rvc(G) atau (rainbow vertex connected) merupakan jumlah warna terkecil yang diperlukan untuk membuat    titik terhubung pelangi dimana :
( ) ≥ ( ) − 1.

## 2.2 Bilangan Terhubung Titik Pelangi Kuat
Li  dan  Shi  [7]  memperkenalkan  mengenai  bilangan  terhubung  titik  pelangi  kuat  yang dinyatakan pada Lemma 2.
Lemma 2 . Misalkan   merupakan graf terhubung tak trivial berorde  , maka :
( ) − 1 ≤ ( ) ≤ ( ).

## 3. Hasil dan Pembahasan
Graf Octa-Chain merupakan  adalah  graf  yang  dibentuk  dari  modifikasi  graf  lingkaran dengan menambahkan suatu sisi yang menghubungkan titik-titik tengah di dimana titik-titiknya akan diwarnai dengan minimum warna- k sehingga menghasilkan lintasan pelangi. Misalkan   adalah bilangan bulat positif dengan ≥ 2 dan adalah graf Octa-Chain dengan 6m+2 titik. Graf Octa- Chain memiliki diameter sebesar 2m+1 dan dinotasikan dengan diam(G). Graf Octa-Chain ( ) terbentuk dari himpunan titik dan sisi yang dikonstruksikan sebagai berikut :
( ) = { | ∈ [1,6 + 2]} ( ) = { | ∈ [1,6 + 2]} ∪ { , } ∪ { , │ ∈ [3, + 1] { , } ∪ { , │ ∈ [2, + 1]
Dari  pendefinisian  himpunan  titik  dan  sisi  diatas,  maka  sebuah  graf Octa-Chain dapat dikonstruksikan dengan titik   sebanyak 6 + 2 titik dan 6 + 2 sisi. Selanjutnya konstruksi graf Octa-Chain dilanjutkan dengan menggambarkan bagian sisi chain yang  menjadi penghubung graf Octa-Chain . Untuk lebih jelasnya konstruksi dari gambar graf Octa-Chain dapat dilihat pada gambar graf berikut:
Gambar 2. Graf

## 3.1 Bilangan Terhubung Titik Pelangi Graf Octa-Chain ( )
Pembahasan tentang bilangan terhubung titik pelangi graf Octa-Chain ( ) dinyatakan pada Teorema 3 beserta pembuktiannya.
Teorema 3 . Misalkan m merupakan bilangan bulat positif dimana ≥ 2 dan adalah graf Octa-
Chain , maka
( ) = 2 .
Bukti: Didefinisikan pewarnaan : ( ) → {1,2,3, … ,2 } sebagai berikut:
= , ∈ [1,3] = 1, ∈ [1, ] = 2 − 2,   ∈ [2, + 1] = 2 − 1, ∈ [2, ] = 2 = 2 , = + 2 = 2 − 1, = + 2 , = 2 − 1,   ∈ [2, ] = 2 − 2, ∈ [2, ] Pewarnaan titik  pelangi graf Octa-Chain , berturut-turut ditampilkan pada Gambar 3 dan Gambar 4.
Gambar 3. Pewarnaan titik pelangi graf
Gambar 4. Pewarnaan titik pelangi graf
Lintasan pelangi untuk setiap pasang titik , ∈ ( ) dengan pewarnaan c pada graf Octa- Chain ( ) dapat dilihat pada Tabel 1.
Berdasarkan Tabel 1 terlihat bahwa setiap pasang titik , ∈ ( ) memiliki lintasan pelangi dengan pewarnaan c pada graf Octa-Chain ( ) . Jadi, terbukti bahwa rvc ( ) = 2 . ∎
3.2 Bilangan Terhubung Titik Pelangi Kuat Graf Octa-Chain ( )
Pembahasan  tentang  bilangan  terhubung  titik  pelangi  kuat  graf octa-chain ( ) disajikan pada Teorema 4.
Teorema 4 . Misalkan m merupakan bilangan bulat positif dimana ≥ 2 dan adalah graf Octa- Chain, maka
( ) = ( ) = 2 .
Bukti: Didefinisikan pewarnaan : ( ) → {1,2,3, … ,2 } sebagai berikut:
Kasus  x y Kondisi Lintasan Titik Pelangi 1 ∈ [2, ] , , , , 2 ∈ [2, − 1], , , , , …, ∈ [3, ] , , ≤ , ≥ 3 3 , ∈ [2, ] , , , , , …, ≤ , 4 , ∈ [2, ] , , , , , …, ≤ , 5 ∈ [2, + 1] , , , , 6 , , , 7 ∈ [2, ] , , , 8 ∈ [2, ] , , , 9 , , , , 10 ∈ [3, ] , , , , ≥ 3 11 ∈ [3, ] , , , , …, ≥ 3 , 12 , ∈ [4, ] , , , , , , ≤ , ≥ 4 … , , , 13 ∈ [2, ] , … , , 14 , ∈ [2, ], , , , < , … , , , 15 , ∈ [2, ], , , , ≤ , , … , , 16 , ∈ [2, ], , , , , ≤ … , , 17 , ∈ [2, ], , , , , … , , ≤
= , ∈ [1,3] = 1, ∈ [1, ] = 2 − 2,   ∈ [2, + 1] = 2 − 1, ∈ [2, ] = 2 = 2 , = + 2 = 2 − 1, = + 2 , = 2 − 1,   ∈ [2, ] = 2 − 2, ∈ [2, ]
Pewarnaan  titik  pelangi  graf Octa-Chain
, dan berturut-turut  ditampilkan  pada Gambar 5 dan Gambar 6.
Gambar 5. Pewarnaan titik pelangi kuat graf
Gambar 6. Pewarnaan titik pelangi graf
Lintasan  pelangi  untuk setiap  pasang  titik , ∈ ( ) dengan  pewarnaan c pada  graf  Octa- Chain ( ) dapat dilihat pada Tabel 2.
Tabel 2. Lintasan pelangi kuat graf Octa-Chain ( ) Kasus Kondisi Lintasan Titik Pelangi Kuat 1 ∈ [2, ] , , , , 2 ∈ [2, − 1], , , , , …, ∈ [3, ] , , ≤ , ≥ 3 3 , ∈ [2, ] , , , , , …, ≤ , 4 , ∈ [2, ] , , , , , …, ≤ , 5 , , , , 6 ∈ [2, ] , , , ,
Kasus Kondisi Lintasan Titik Pelangi Kuat 7 ∈ [2, ] , , , , , 8 , , , 9 ∈ [2, ] . , , 10 ∈ [2, ] . , , 11 , , , , 12 ∈ [3, ], , , , , ≥ 3 13 ∈ [2, ] , , , 14 ∈ [3, ], , , , ≥ 3 , 15 , ∈ [4, ] , , , , , , ≤ , ≥ 4 … , , , 16 ∈ [2, ] , … , , , 17 , ∈ [2, ], , , , < , … , , , 18 , ∈ [2, ], , , , ≤ , , … , 19 , ∈ [2, ], , , , , ≤ … , , 20 , ∈ [2, ], , , , , … , , ≤
Berdasarkan  Tabel  2  terlihat  bahwa setiap  pasang  titik , ∈ ( ) selalu  memiliki  lintasan pelangi  dengan  pewarnaan c pada  graf Octa-Chain ( ) .  Jadi,  terbukti  bahwa rvc ( ) = ( ) = 2 . ∎

## 4. Kesimpulan
Berdasarkan hasil dan pembahasan penelitian menunjukkan bahwa bilangan terhubung titik pelangi  dari  graf Octa-Chain adalah 2m dan  bilangan  terhubung  titik  pelangi  kuat dari  graf Octa- Chain adalah 2m , dimana   merupakan bilangan bulat positif dan ≥ 2.

## Referensi
[1]   R. Munir, Matematika Diskrit , Bandung: Informatika, 2010.
[2]   I. K. Budayasa, Teori Graph dan Aplikasinya, Surabaya: UNESA University Press, 2007.
[3]   J. A. Gallian, "A Dynamic Survey Of Graph Labelling," Electronic Journal of Combinatorics, 2018.
[4]   M. Kubale, Graph Coloring , AMS Bookstore, 2004.
[5]   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.
[6]   M. Krivelevich and R. Yuster, "The Rainbow Connection of a Graph Is (at Most) Reciprocal to Its Minimum Degree," Journal of Graph Theory, vol. 07, pp. 84-99, 2009.
[7]   X.  Li,  Y.  Mao  and  Y.  Shi,  "The  strong  rainbow  vertex  connection  of  graphs," Utilitas Mathematica, vol. 93, pp. 213-223, 2014.
[8]   M.  Afifuddin  and  I.  K.  Budayasa,  "Bilangan  Keterhubungan  Titik  Pelangi  Kuat Pada  Graf," MATH  Unesa  Jurnal  Ilmiah  Matematika, vol.  10,  no.  1,  pp.  33-40,  2022. doi: https://doi.org/10.26740/mathunesa.v10n1.p33-40
[9]   I. Lihawa, S. Ismail, I. K. Hasan, L. Yahya, S. K. Nasib and N. I. Yahya, "Bilangan Terhubung Titik Pelangi pada Graf Hasi lOperasi Korona Graf Prisma (Pm,2) dan Graf Lintasan," Jambura. J. Math., vol. 4, no. 1, pp. 145-151, 2022. doi: https://doi.org/10.34312/jjom.v4i1.11826
[10] D.  N.  Simamora  and  A.  Salman,  "The  Rainbow  (Vertex)  Connection  Number  of  Pencil Graphs," Procedia Computer Science, vol. 74, pp. 138–142, 2015. doi: https://doi.org/10.1016/j.procs.2015.12.089
[11] A. W. Bustan and A. Salman, "The Rainbow Vertex-Connection Number of Star Fan Graphs," CAUCHY–Jurnal  Matematika  Murni  dan  Aplikasi, vol.  5,  no.  3,  pp.  112-116,  2018.  doi: https://doi.org/10.18860/ca.v5i3.5516
[12] A. F. Akadji, M. R. Katili, S. K. Nasib and N. I. Yahya, "Rainbow vertex connection number and  strong  rainbow  vertex  connection  number  on  slinky  graph  (SlnC4)," DESIMAL:  Jurnal Matematika, vol. 4, pp. 123-132, 2021.doi: https://doi.org/10.24042/djm.v4i2.7276
[13] R. Diestel, Graph Theory , 4th Edition, Springer, 2010.