Desember 2019, Vol. 7, No. 2, Hal. 56-61 Journal Homepage: http://ejurnal.ung.ac.id/index.php/Euler DOI: https://doi.org/10.34312/euler.v7i2.10345

## BILANGAN TERHUBUNG TITIK PELANGI PADA AMALGAMASI GRAF BERLIAN
Afifah Farhanah Akadji 1* , Dennynatalis Taha 2 , Narti Lakisa 3 , Nisky Imansyah Yahya 4
1,2,3,4 Jurusan Matematika, Universitas Negeri Gorontalo, Bone Bolango 96119, Indonesia *Penulis Korespondensi. Email: farhanah.akadji@gmail.com

## Abstrak
Misalkan  terdapat  suatu  graf  sederhana,  terbatas,  dan  berhingga 𝐺 = (𝑉, 𝐸). Pewarnaan  titik 𝑐 dinotasikan dengan 𝑐: 𝐸(𝐺) → {1,2, . . . , 𝑘} dengan 𝑘 banyaknya pewarnaan pelangi pada graf 𝐺 . Suatu  graf  dikatakan  terhubung  pelangi  apabila  setiap  pasang  titik 𝑥 dan 𝑦 terdapat  lintasan pelangi.  Sebuah  lintasan  dikatakan  pelangi  apabila  tidak  terdapat  dua  buah  sisi  yang  memiliki warna  yang  sama  dalam  satu  lintasan.  Bilangan  terhubung  pelangi  graf 𝐺 dinotasikan  dengan 𝑟𝑐(𝐺) adalah bilangan bulat positif terkecil- 𝑘 yang membuat graf 𝐺 memiliki pewarnaan pelangi. Selanjutnya, graf dikatakan terhubung titik pelangi apabila pada setiap pasang titik 𝑥 dan 𝑦 tidak terdapat dua buah titik yang memiliki warna yang sama dalam satu lintasan. Bilangan terhubung titik  pelangi  graf 𝐺 dinotasikan  dengan 𝑟𝑣𝑐(𝐺) adalah  bilangan  bulat  positif  terkecil- 𝑘 yang membuat  graf 𝐺 memiliki  pewarnaan  pelangi.  Pada  makalah  ini  dibahas  tentang  bilangan terhubung  titik  pelangi  pada  amalgamasi  graf  berlian.    Graf  berlian  dengan 2𝑛 titik  dinotasikan dengan 𝐵𝑟 𝑛 dan amalgamasi graf berlian 𝐵𝑟 𝑛 dengan menambahkan penggandaan graf sebanyak t pada titik v dinotasikan dengan 𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡) .
Kata Kunci: Bilangan Terhubung Titik Pelangi; Amalgamasi; Graf Berlian

## Abstract
Suppose there is a simple, and finite graph G = (V, E). The coloring of vertices c is denoted by c: E(G) → {1,2, ..., k} with k  is the number of rainbow colors on graph G. A graph is said to be rainbow  connected  if  every  pair  of  points  x  and  y  has  a  rainbow  path.  A  path  is  said  to  be  a rainbow if there are not two edges that have the same color in one path. The rainbow connected number of graph G denoted by rc (G) is the smallest positive integer-k which makes graph G has rainbow coloring. Furthermore, a graph is said to be connected to rainbow vertex if at each pair of vertices x and y there are not two vertices that have the same color in one path. The rainbow vertex connected number of graph G is denoted by rvc (G) is the smallest positive integer-k which makes the graph G has rainbow coloring. This paper discusses rainbow vertex connected number in the amalgamation of a diamond graph. A diamond graph with 2n points is denoted by 𝐵𝑟 𝑛 and amalgamation  of a  diamond graph 𝐵𝑟 𝑛 by  adding  the  multiplication  of  the  graph  t at  point v  is denoted by 𝐴𝑚𝑎𝑙 (𝐵𝑟 𝑛 , 𝑣, 𝑡) .
Keywords: Rainbow Vertex Connected Number; Amalgamation; Diamond Graph

## 1. Pendahuluan
Teori  graf  adalah  salah  satu  cabang  ilmu  matematika  yang  mempelajari  tentang  sifat-sifat graf. Graf yang digunakan untuk merepresentasikan objek-objek diskrit pada matematika memiliki beberapa  operasi  seperti  penjumlahan  graf,  perkalian  graf,  dan  amalgamasi  [1].  Amalgamasi merupakan penggandaan graf yang dipusatkan pada satu elemen dari graf tersebut [2].
Seiring  perkembangannya,  topik  penelitian  cabang  teori  graf  semakin  luas.  Salah  satu topiknya yaitu bilangan terhubung pelangi. Bilangan terhubung pelangi pertama kali diperkenalkan oleh  seorang  matematikawan  bernama  Chartrand  pada  tahun  2008  [3].  Pada  tahun  2009,  topik bilangan  terhubung  pelangi  ini  kemudian  dikembangkan  oleh  Krivelevich  dan  Yuster  [4]  yang
memperkenalkan  bilangan  terhubung  titik  pelangi  yang  merupakan  bilangan  terkecil  yang  dapat membuat  sebuah  graf  memiliki  lintasan  pelangi  pada  setiap  pasang  titiknya.  Diameter  merupakan jarak terbesar dari seluruh pasang titik yang dinotasikan dengan 𝑑𝑖𝑎𝑚(𝐺) . Misalkan 𝑚 merupakan banyaknya titik pada graf 𝐺 , sehingga
𝑑𝑖𝑎𝑚(𝐺) − 1 ≤ 𝑟𝑣𝑐(𝐺) ≤ 𝑚 − 2 (1)
Pada penelitian sebelumnya, telah diteliti bilangan terhubung pelangi pada graf berlian ( 𝐵𝑟 𝑛 ) yang  diteliti  oleh  Shulhany  dan  Salman  [5].  Dengan  menggunakan  operasi  amalgamasi  pada  graf berlian ( 𝐵𝑟 𝑛 ), penelitian ini akan membahas bilangan terhubung titik pelangi pada amalgamasi graf berlian ( 𝐵𝑟 𝑛 ).

## 2. Metode Penelitian
Penelitian  ini  menggunakan  metode  penelitian  studi  literatur  (library  research).  Pada penelitian ini dilakukan kajian terhadap buku, textbook, jurnal, dan artikel-artikel ilmiah mengenai amalgamasi dan graf berlian. Adapun langkah-langkah yang dilakukan adalah
1. Menggambar bentuk amalgamasi graf berlian
2. Menentukan pewarnaan titik amalgamasi graf berlian, dan
3. Membuktikan teorema

## 3. Hasil dan Pembahasan
Graf berlian dinotasikan dengan 𝐵𝑟 𝑛 dengan definisi sisi dan titik sebagai berikut:
𝑉(𝐵𝑟 𝑛 ) = {𝑣} ∪ {𝑣 𝑖 |𝑖 ∈ {1,2, … , 𝑛}} ∪ {𝑢 𝑖 |𝑖 ∈ {1,2, … 𝑛 − 1}}
𝐸(𝐵𝑟 𝑛 ) = {𝑣𝑣 𝑖 |𝑖 ∈ {1,2, … , 𝑛}} ∪ {𝑣 𝑖 𝑣 𝑖+1 |𝑖 ∈ {1,2, … , 𝑛 − 1}} ∪ {𝑢 𝑖 𝑢 𝑖+1 |𝑖 ∈ {1,2, … , 𝑛 − 2}} ∪ {𝑢 𝑖 𝑣 𝑖 |𝑖 ∈ {1,2, … , 𝑛 − 1}} ∪ {𝑢 𝑖 𝑣 𝑖−1 |𝑖 ∈ {1,2, … , 𝑛 − 1}}
Amalgamasi graf berlian (𝐵𝑟 𝑛 ) sebanyak 𝑡 dengan 𝑣 adalah titik terminal dinotasikan dengan 𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡) dengan 𝑛 ≥ 4 . 𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡) memiliki  diameter = 𝑑𝑖𝑎𝑚(𝐺) = 4 dan didefinisikan oleh:
𝑉(𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡)) = { 𝑢 𝑖,𝑗 , 𝑖 ∈ [1, 𝑡] 𝑗 ∈ [1, 𝑛 − 1] 𝑣 𝑖,𝑗 , 𝑖 ∈ {1, 𝑡] 𝑗 ∈ [1, 𝑛]
𝑣 𝐸(𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡)) =
{ 𝑢 𝑖,𝑗 𝑢 𝑖,𝑗+1 ; 𝑖 ∈ [1, 𝑡], 𝑗 ∈ [1, 𝑛 − 2] 𝑣 𝑖,𝑗 𝑣 𝑖,𝑗+1 ; 𝑖 ∈ [1, 𝑡], 𝑗 ∈ [1, 𝑛 − 1]
𝑢 𝑖,𝑗 𝑣 𝑖,𝑗 ; 𝑖 ∈ [1, 𝑡], 𝑗 ∈ [1, 𝑛 − 1]
𝑢 𝑖,𝑗 𝑣 𝑖,𝑗+1 ; 𝑖 ∈ [1, 𝑡], 𝑗 ∈ [1, 𝑛 − 1] 𝑣 𝑖,𝑗 𝑣; 𝑖 ∈ [1, 𝑡], 𝑗 ∈ [1, 𝑛]
Gambar graf berlian 𝐵𝑟 4 dan 𝐴𝑚𝑎𝑙(𝐵𝑟 4 , 𝑣, 2) berturut-turut ditunjukkan pada Gambar 1 dan Gambar 2.
Gambar 1. Graf Berlian 𝐵𝑟 4
Gambar 2. 𝐴𝑚𝑎𝑙(𝐵𝑟 4 , 𝑣, 2)

## Teorema 1
Misalkan 𝐺 ≅ 𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡) dengan bilangan bulat 𝑛 ≥ 4 dan 𝑡 ≥ 2 . Maka bilangan terhubung titik pelangi adalah
rvc(𝐺) = diam(𝐺) = 4 (2)

## Bukti:
Definisikan pewarnaan 𝑐: 𝐸(𝐺) → {1,2,3,4} sebagai berikut:
𝑐(𝐸(𝐺)) =
{ 𝑢 𝑖,𝑗 = (𝑗 + 1) mod 2 + 1; 𝑣 𝑖,𝑗 = 𝑗 mod 2 + 3;
𝑣 𝑖,1 =  2; 𝑣 = 1;
𝑖 ∈ [1, 𝑡],
𝑖 ∈ [1, 𝑡], 𝑖 ∈ [1, 𝑡], 𝑗 ∈ [1, 𝑛 − 1] 𝑗 ∈ [2, 𝑛]
Selanjutnya,  akan  ditunjukkan  bahwa  untuk  setiap 𝑥 dan 𝑦 di 𝑉(𝐴𝑚𝑎𝑙(𝐵𝑟 𝑛 , 𝑣, 𝑡)) dengan 𝑑𝑖𝑎𝑚(𝑥, 𝑦) ≥ 3 , terdapat lintasan pelangi 𝑥 − 𝑦 .
Gambar 3. Pewarnaan pelangi Amal(𝐵𝑟 4 , 𝑣, 2)
Kasus  1. Untuk 𝑖 ∈ [1, 𝑡] ,  dan 𝑗 ∈ [1, 𝑛 − 4] ,  Jika 𝑥 = 𝑢 𝑖,𝑗 dan 𝑦 = 𝑢 𝑖,𝑗+3 ,  untuk 𝑛 ≥ 5 ,  maka terdapat lintasan 𝑢 𝑖,𝑗 , 𝑢 𝑖,𝑗+1 , 𝑢 𝑖,𝑗+2 , 𝑢 𝑖,𝑗+3 .
Kasus  2. Untuk 𝑖 ∈ [1, 𝑡] ,  dan 𝑗 ∈ [1, 𝑛 − 5] ,  Jika 𝑥 = 𝑢 𝑖,𝑗 dan 𝑦 = 𝑢 𝑖,𝑗+4 ,  untuk 𝑛 ≥ 6 ,  maka terdapat lintasan 𝑢 𝑖,𝑗 , 𝑢 𝑖,𝑗+1 , 𝑢 𝑖,𝑗+2 , 𝑢 𝑖,𝑗+3 , 𝑢 𝑖,𝑗+4 .
Kasus 3. Untuk 𝑖 ∈ [1, 𝑡] , dan 𝑗, 𝑘 ∈ [1, 𝑛] dengan 𝑗 < 𝑘 , Jika 𝑥 = 𝑢 𝑖,𝑗 dan 𝑦 = 𝑣 𝑖,𝑘 , maka terdapat lintasan 𝑢 𝑖,𝑗 , 𝑣 𝑖,𝑗 , 𝑣, 𝑣 𝑖,𝑘 .
Kasus 4. Untuk 𝑖 ∈ [1, 𝑡 − 1], 𝑘 ∈ [𝑖 + 1, 𝑡] , dan 𝑗, 𝑙 ∈ [1, 𝑛 − 1]
Subkasus 4.1. Jika 𝑥 = 𝑢 𝑖,𝑗 dan 𝑦 = 𝑣 𝑘,𝑙 , maka terdapat lintasan 𝑢 𝑖,𝑗 , 𝑣 𝑖,𝑗 , 𝑣, 𝑣 𝑘,𝑙 .
Subkasus 4.2. Jika 𝑥 = 𝑣 𝑖,𝑗 dan 𝑦 = 𝑢 𝑘,𝑙 , maka terdapat lintasan 𝑣 𝑖,𝑗 , 𝑣, 𝑣 𝑘,𝑙 , 𝑢 𝑘,𝑙 .
Kasus 5. Untuk 𝑖 ∈ [1, 𝑡 − 1], 𝑘 ∈ [𝑖 + 1, 𝑡], dan 𝑗, 𝑙 ∈ [1, 𝑛 − 1]
Subkasus  5.1. Jika 𝑥 = 𝑢 𝑖,𝑗 dan 𝑦 = 𝑢 𝑘,𝑙 ,  dengan 𝑗 dan 𝑙 memiliki  varitas  yang  sama  maka terdapat lintasan 𝑢 𝑖,𝑗 , 𝑣 𝑖,𝑗 , 𝑣, 𝑣 𝑘,𝑙+1 , 𝑢 𝑘,𝑙 .
Subkasus  5.2. Jika 𝑥 = 𝑢 𝑖,𝑗 dan 𝑦 = 𝑢 𝑘,𝑙 ,  dengan 𝑗 dan 𝑙 memiliki  varitas  yang  berbeda  maka terdapat lintasan 𝑢 𝑖,𝑗 , 𝑣 𝑖,𝑗 , 𝑣, 𝑣 𝑘,𝑙 , 𝑢 𝑘,𝑙 .
Kasus 6. Untuk 𝑖 ∈ [1, 𝑡] dan 𝑗, 𝑘 ∈ [1, 𝑛 − 1] dengan 𝑗 < 𝑘 , untuk 𝑛 ≥ 6, maka terdapat lintasan 𝑢 𝑖,𝑗 , 𝑣 𝑖,𝑗 , 𝑣, 𝑣 𝑖,𝑘 , 𝑢 𝑖,𝑘 .
Graf hasil pewarnaan masing-masing ditampilkan pada Gambar 3, Gambar 4, dan Gambar 5.
Gambar 4. Pewarnaan pelangi Amal ( 𝐵𝑟 5 , 𝑣, 3 )

## 4. Kesimpulan
Bilangan  terhubung  titik  pelangi  untuk  amalgamasi  graf  berlian Amal(𝐵𝑟 𝑛 , 𝑣, 𝑡) sama dengan  diameter  graf.  Sehingga,  diperoleh  bilangan  terhubung  titik  pelangi  pada  amalgamasi  graf berlian yaitu
rvc(Amal(𝐵𝑟 𝑛 , 𝑣, 𝑡)) = diam(𝐺) = 4

## Referensi
[1]  Hasmawati,  “Dekomposisi  Graf  Hasil  Kali  Tiga  Lintasan  ke  Dalam  Sub  Graf  Perentang Reguler,” J. Mat. Stat. dan Komputasi , vol. 10, no. 1, pp. 14–25, 2013.
[2]  J.  L.  Gross,  I.  F.  Khan,  and  M.  I.  Poshni,  “Genus  Distribution  of  Graph  Amalgamations: Pasting at Root-Vertices,” ars Comb., vol. 94, pp. 33–353, 2010.
[3]  G.  Chartrand et  al. ,  “RAINBOW  CONNECTION  IN  GRAPHS,” J.  Comb.  Math.  Comb. Comput. , vol. 1, pp. 85–98, 2008.
[4]  M. Krivelevich and R. Yuster, “The Rainbow Connection of a Graph Is (at Most) Reciprocal to Its Minimum Degree Michael,” J. Graph Theory , vol. 63, pp. 185–191, 2009.
[5]  M.  A.  Shulhany  and  A.  N.  M.  Salman,  “Bilangan  Terhubung  Pelangi  Graf  Berlian,”  in Prosiding  Seminar  Nasional  Matematika  dan  Pendidikan  Matematika  UMS ,  pp.  916–923, 2015.