## Bilangan Kromatik Dominasi pada Graf-Graf Hasil Operasi Korona
Muh. Alwan Hadi, Dr. Darmaji, S.Si., M.T., Drs. Suhud Wahyudi, M.Si. Jurusan Matematika, Fakultas MIPA, Institut Teknologi Sepuluh Nopember (ITS)
Jl. Arief Rahman Hakim, Surabaya 60111 Indonesia
e-mail : darmaji@matematika.its.ac.id
Abstrak—Diberikan graf 𝑮 (𝑽 , 𝑬) , pewarnaan kromatik  dominasi  ialah  pewarnaaan  simpul  (proper coloring)  graf 𝑮 dengan  tambahan  sifat  setiap  simpul mendominasi  semua  kelas  warna.  Warna  minimum  yang digunakan  dalam  pewarnaan  kromatik  dominasi  graf 𝑮 disebut  bilangan  kromatik  dominasi  graf 𝑮 dinotasikan dengan 𝝌 𝒅 (𝑮) .  Makalah  ini  membahas  bagaimana mendapatkan  kromatik  dominasi  dari  graf 𝑮 dengan 𝑮 adalah  graf  hasil  operasi  korona  dari  dua  graf  yakni Lintasan dan Lingkaran. Selain itu, dibahas juga graf hasil operasi  korona  antara  Graf  lengkap  dengan  Lintasan  dan Lingkaran.  Berdasarkan  pengamatan  didapatkan  bahwa Bilangan  kromatik  dominasi 𝝌 𝒅 (𝑮 𝒎 ⊙ 𝑷 𝒏 )   = |𝑽 (𝑮𝒎)|   + 𝟐, untuk 𝒎 ≥  𝟏 , 𝒏 ≥  𝟐 dengan 𝑮 𝒎 graf  terhubung  order 𝒎 dan 𝑷 𝒏 Lintasan  order 𝒏 ,  dan 𝝌 𝒅 (𝑮 𝒎 ⊙   𝑪 𝒏 )   = |𝑽 (𝑮𝒎)|   +  𝟐 ,  dan  | 𝑽 (𝑮𝒎)|   +  𝟑 ,  berturut-turut  untuk 𝒏 genap, dan 𝒏 gasal dengan 𝑪 𝒏 Lingkaran order 𝒏 .
Kata Kunci—Bilangan Kromatik Dominasi, Graf Lengkap,  Kromatik  Dominasi,  Lingkaran,  Lintasan, Operasi Korona.

## I. PENDAHULUAN
eori  graf  adalah  salah  satu  cabang  dari  ilmu matematika.  Secara  matematis,  suatu  graf 𝐺 didefinisikan sebagai pasangan himpunan ( 𝑉, 𝐸 ) dengan 𝑉 adalah  himpunan  simpul  ( vertex )  yang  tidak  kosong dan 𝐸 adalah himpunan boleh kosong yang menghubungkan  simpul  dan  disebut  sisi  ( edge ). Selanjutnya  himpunan  simpul  dari  graf 𝐺 ditulis 𝑉 (𝐺) dan himpunan sisi dari graf 𝐺 ditulis 𝐸(𝐺) [1] .
Salah satu topik yang menjadi kajian teori graf adalah himpunan  dominasi  ( dominating  set )  dan  bilangan dominasi  ( dominating  number ).  Himpunan  dominasi  ( 𝑆 ) pada graf 𝐺 adalah subset dari 𝑉 (𝐺) sedemikian hingga setiap  simpul 𝐺 yang  bukan  elemen 𝑆 terhubung  dan berjarak satu terhadap 𝑆 . Kardinalitas minimum di antara himpunan  dominasi  pada  graf 𝐺 disebut  bilangan dominasi  dari  graf 𝐺 dan  dinotasikan  dengan 𝛾(𝐺) [2] . Oleh karena itu, bilangan dominasi sangat erat kaitannya dengan himpunan dominasi.
Sejarah dominasi ( dominating ) pada graf dimulai pada awal tahun 1850 sejak pemain catur eropa antusias untuk menyelesaikan  masalah dominating  queens .  Dalam masalah  ini,  dominasi  digunakan  untuk  menentukan banyaknya queen sedemikian  setiap queen bisa mendominasi atau menyerang setiap posisi dengan sekali perpindahan  pada  papan  catur  berukuran 8  ×  8 .  Dalam teori  graf, queens direpresentasikan  sebagai  simpul  dan jalur  perpindahan  antara  kotak  pada  papan  catur dianggap  sebagai  sisi  [2].  Go  dan  Canoy  telah menunjukkan  bilangan  dominasi  pada  graf  hasil  operasi
korona.
Teorema I.1. Diberikan dua graf terhubung 𝐺 𝑚 dan 𝐻 𝑛 dengan  masing-masing  ordernya 𝑚 dan 𝑛 dengan 𝑚, 𝑛 ≥  1 ,  maka  bilangan  dominasi  dari  graf  hasil operasi korona 𝐺 ⊙ 𝐻 adalah 𝛾(𝐺 𝑚 ⊙ 𝐻 𝑛 ) =  𝑚 [3].
Pewarnaan  graf  dibagi  menjadi  dua  macam  yaitu pewarnaan  sisi  dan  pewarnaan  simpul.  Makalah  ini dikhususkan  pada  pembahasan  pewarnaan  simpul. Pewarnaan simpul diartikan sebagai memberi warna pada setiap simpul graf sehingga dua simpul yang bertetangga memiliki  warna  yang  berbeda.  Suatu  graf 𝐺 dikatakan memiliki 𝑘 -pewarnaan  apabila  graf 𝐺 dapat  diwarnai dengan 𝑘 warna.  Pemberian  warna  pada  graf  haruslah seminimal  mungkin,  warna  minimal  yang  digunakan untuk mewarnai graf 𝐺 disebut bilangan kromatik 𝜒(𝐺).
Pewarnaan  graf  dapat  diaplikasikan  dalam  berbagai masalah  kehidupan  sehari-hari.  Beberapa  diantaranya yakni  penjadwalan  mata  kuliah,  pengaturan  lampu lalulintas, penjadwalan acara televisi dan lain-lain [4].
Kromatik  dominasi  merupakan  perpaduan  antara  dua konsep  teori  graf  yakni  konsep  pewarnaan  simpul  dan konsep  himpunan  dominasi.  Konsep  ini  pertama  kali diperkenalkan oleh Relucca Gera [5]. Kromatik dominasi diartikan sebagai pewarnaan simpul dengan setiap simpul mendominasi  setiap  simpul  dari  beberapa  kelas  warna. Kardinalitas  minimum  dari  kelas  warna  pada  kromatik dominasi graf 𝐺 disebut bilangan kromatik dominasi dari graf 𝐺 dan dinotasikan 𝜒 𝑑 (𝐺) .
Definisi  I.2.  Sebuah  simpul 𝑣 ∈  𝑉 merupakan dominator  dari  himpunan 𝑆  ⊆  𝑉 jika 𝑣 mendominasi setiap  simpul 𝑆 .  Partisi 𝜙  = {𝑉 1 , 𝑉 2 , … 𝑉 𝑘 } disebut dominator  partisi  jika  setiap  simpul 𝑣 ∈  𝑉 merupakan dominator pada paling sedikitnya satu dari 𝑉 𝑖 . Bilangan Dominasi partisi 𝜙 𝑑 sama  dengan 𝑘 minimum  sehingga 𝐺 memiliki  dominasi  partisi  dengan  order 𝑘 .  Jika selanjutnya 𝜙 dijadikan  pewarnaan  simpul  maka pewarnaan  tersebut  disebut  pewarnaan  dominasi (dominator  coloring) 𝐺 .  Bilangan  kromatik  Dominasi 𝜒 𝑑 (𝐺) adalah  banyak  warna  minimum  yang  digunakan pada pewarnaan dominasi [6].
Operasi  antara  dua  buah  graf  merupakan  salah  satu cara  untuk mendapatkan  bentuk graf-graf  baru. Terdapat  berba-  gai    jenis  operasi  didalam  graf diantaranya  yakni  join (+) ,  gabungan (∪) ,   kartesian (×) ,  korona (⊙) dan  operasi  comb (⊳) .    Sebagai contoh  graf  grid  merupakan  hasil  dari  operasi kartesian  dua  buah  Lintasan.  Roda 𝑊 𝑛 merupakan hasil  dari operasi korona graf lengkap 𝐾1 dengan 𝐶 𝑛 .
T
Penelitian  mengenai  kromatik  dominasi  dan  bilangan kromatik  dominasi  telah  banyak  dilakukan  antara  lain, telah  diteliti  bilangan  kromatik  dominasi  untuk  graf hypercube 𝑄 𝑛 =   𝑄 𝑛−1 × 𝑘 2 (dengan 𝑄 1 ≌   𝑃 2 , 𝑛    2 ) dan  beberapa  graf bipartite [7].  Graf  bintang 𝐾 1,𝑛 dan graf  lengkap 𝐾 𝑛 memiliki 𝜒 𝑑 (𝐾 1,𝑛 )   =  2, 𝜒 𝑑 (𝐾 𝑛 )   =  𝑛 dan χ d (P n ) =  1 + ⌈ n
3 ⌉ untuk 𝑛  =  2, 3, 4, 5, 7 dan χ d (P n ) = 2 +  ⌈ n 3 ⌉ untuk 𝑛 yang  lain.  Lingkaran 𝐶 𝑛 memiliki 𝜒 𝑑 (𝐶 𝑛 )   =   ⌈ 𝑛 3 ⌉ untuk 𝑛  =  4 , 𝜒 𝑑 (𝐶 𝑛 ) =  1 ⌈ 𝑛 3 ⌉
untuk 𝑛  =  5 dan 𝜒 𝑑 (𝐶 𝑛 ) = 2 + ⌈ 𝑛 3 ⌉ untuk 𝑛 yang lain.
Graf roda 𝑊 1,𝑛 memiliki 𝜒 𝑑 (𝑊 1,𝑛 )   =  3 untuk 𝑛 genap dan 𝜒 𝑑 (𝑊 1,𝑛 )   =  4 untuk 𝑛 gasal. Graf lengkap k-partite 𝐾 𝑎 1 ,𝑎 2 ,…,𝑎 𝑘 memiliki 𝜒 𝑑 (𝐾 𝑎1 , … 𝐾 𝑎𝑘 ) = k [8]. Salah satu topik  mengenai  bilangan  kromatik  dominasi  graf  yang belum  diteliti  adalah  jika  dua  graf  sederhana  dikenakan operasi  korona  kemudian  hasil  operasi  tersebut  dicari bilangan  kromatik  dominasinya.  Oleh  karena  itu,  dalam penelitian  ini  akan  ditentukan  bilangan  kromatik dominasi 𝜒 𝑑 (𝐺) graf  hasil  operasi  korona  dari  graf sederhana.

## II. HASIL DAN PEMBAHASAN
Pada  bagian  ini  dibahas  bilangan  kromatik  dominasi pada  graf  hasil  operasi  korona  dari  Lintasan  dan Lingkaran yakni 𝑃 𝑚 ⊙   𝑃 𝑛 , 𝑃 𝑚 ⊙   𝐶 𝑛 , 𝐶 𝑚 ⊙   𝑃 𝑚 , dan 𝐶 𝑚 ⊙   𝐶 𝑛 . Selanjutnya 𝐾 𝑚 ⊙   𝑃 𝑛 , 𝐾 𝑚 ⊙   𝐶 𝑛 , sehingga  didapatkan  bentuk  umum  dari  bilangan kromatik  dominasi  pada  graf  hasil  operasi  korona  dari ebarang graf ( 𝐺 𝑚 ) dengan graf Lintasan dan Lingkaran.
Kromatik Dominasi Lintasan dengan Lintasan
Observasi  II.1 ( Kromatik  Dominasi 𝑃 𝑚 ⊙ 𝑃 𝑛 ) Diberikan Lintasan 𝑃 𝑚 dan 𝑃 𝑛 masing-masing memiliki order 𝑚, 𝑛 ≥  2 , 𝑚, 𝑛 ∈   𝑁 . Jika 𝐺 = 𝑃 𝑚 ⊙   𝑃 𝑛 adalah graf  hasil  operasi  korona  dari 𝑃 𝑚 dan 𝑃 𝑛 maka bilangan kromatik dominasi dari 𝜒 𝑑 (𝐺) = |𝑉(𝑃 𝑚 )|   + 2.
Bukti . Misalkan Graf 𝐺 adalah graf hasil korona dari graf 𝑃 𝑚 dan 𝑃 𝑛 ,  yaitu 𝐺 = 𝑃 𝑚 ⊙   𝑃 𝑛 .  Order  dari  Lintasan |𝑃 𝑚 | = 𝑚 dan Lintasan |𝑃 𝑛 |   =  𝑛 . Katakan 𝑣 1 , 𝑣 2 , … , 𝑣 𝑚 adalah simpul-simpul graf 𝑃 𝑚 dan 𝑢 𝑖1 , 𝑢 𝑖2 , … , 𝑢 𝑖𝑛 adalah simpul-simpul 𝑃 𝑛 yang  melekat  dengan  simpul  ke- 𝑣 𝑖 untuk 1 ≤  𝑖 ≤  𝑚 .  Konstruksi  pewarnaan  kromatik dominasi 𝑓 ∶  𝑉(𝐺) →   { 1, 2, 3, … 𝜒 𝑑 (𝐺)} dengan menggunakan | 𝑉(𝑃 𝑚 )|   + 2 warna sebagai berikut : untuk 𝑢 𝑖(2𝑗+1) katakan 𝑓(𝑢 {𝑖(2𝑗+1)} ) =  1 , untuk 𝑢 𝑖(2𝑗) katakan 𝑓(𝑢 𝑖(2𝑗) ) =  2 kemudian untuk 𝑣 𝑖 katakan 𝑓(𝑣 𝑖 )   =  2 + 𝑖 ,  untuk  setiap 1 ≤  𝑖 ≤  𝑚, 0 ≤  𝑗 .  Pewarnaan  ini merupakan pewarnaan kromatik dominasi dari 𝐺 , karena pewarnaan  ini  tetap  merupakan  pewarnaan  simpul ( proper coloring ) dan himpunan dominasi minimum dari graf 𝐺 mendominasi  setiap  simpul  dari  kelas  warna dengan  kata  lain  simpul  dengan  kelas  warna  1  dan  2 bertetangga  dengan  simpul  dengan  warna  yang  unik. Dengan demikian, didapatkan bahwa 𝜒 𝑑 (𝐺)   = |𝑉(𝑃 𝑚 )|   +  2 .
∎
Dengan demikian, Bilangan kromatik dominasi dari graf hasil operasi korona Lintasan  ( 𝑃 𝑚 ) dengan Lintasan ( 𝑃 𝑛 ) hanya  dipengaruhi  oleh  Lintasan  ( 𝑃 𝑚 )  sebab  Lintasan
( 𝑃 𝑛 )  minimal  harus  diwarnai  dengan  2  warna sedangkan Lintasan ( 𝑃 𝑚 ) minimal harus diwarnai sebanyak 𝑚 warna agar memenuhi sifat kromatik dominasi minimum. Lebih jelasnya,  Perhatikan  Contoh  II.1.1  dan  Contoh  II.1.2 berikut ini
Contoh II.1.1 Diberikan Lintasan 𝑃 3 dan 𝑃 4 , Jika Graf 𝐺 1 = 𝑃 3 ⊙   𝑃 4 adalah  graf  hasil  operasi  korona  Lintasan 𝑃 3 dan 𝑃 4 , maka  dengan  menggunakan  Observasi  II.1  maka didapatkan  bahwa 𝜒 𝑑 (𝐺 1 ) = 5 ,  sebagaimana  yang ditunjukkan pada Gambar 1.
Gambar 1. Kromatik dominasi graf 𝐺 1 Contoh II.1.2
Diberikan  Lintasan 𝑃 4 dan 𝑃 5 ,  Graf 𝐺 2 =   𝑃 4 ⊙ 𝑃 5 adalah  graf  hasil  korona  Lintasan 𝑃 6 dan 𝑃 5 ,  maka dengan  menggunakan  Observasi  II.1  maka  didapatkan bahwa 𝜒 𝑑 (𝐺 2 )   =  6 ,  sebagaimana  yang  ditunjukkan
pada Gambar 2.
Gambar 2. Kromatik dominasi graf 𝐺 2 Kromatik Dominasi Lintasan dengan Lingkaran.
Observasi  II.1 ( Kromatik  Dominasi 𝑃 𝑚 ⊙ 𝐶 𝑛 ) Diberikan  Lintasan 𝑃 𝑚 dan  Lingkaran 𝐶 𝑛 masing- masing memiliki order 𝑚 ≥  2 , 𝑛 ≥ 4  𝑚, 𝑛 ∈   𝑁 . Jika 𝐻 adalah graf hasil operasi korona dari 𝑃 𝑚 dan 𝐶 𝑛 maka bilangan kromatik dominasi
𝜒 𝑑 (𝐻)   =
{ |𝑉(𝑃 𝑚 )| + 2 , 𝑛 𝑔𝑒𝑛𝑎𝑝 |𝑉(𝑃 𝑚 )| + 3 , 𝑛 𝑔𝑎𝑠𝑎𝑙
Bukti. Misalkan  Graf 𝐻 adalah  graf  hasil  korona  dari graf 𝑃 𝑚 dan 𝐶 𝑛 ,  yaitu 𝐻 = 𝑃 𝑚 ⊙   𝐶 𝑛 .  Order  dari Lintasan | 𝑃 𝑚 |   =  𝑚 dan  Lingkaran | 𝐶 𝑛 |   =  𝑛 . Katakan 𝑣 1 , 𝑣 2 , … , 𝑣 𝑚 adalah simpul-simpul graf 𝑃 𝑚 dan 𝑢 {𝑖1} , 𝑢 {𝑖2} , … , 𝑢 {𝑖𝑛} adalah  simpul-simpul 𝐶 𝑛 yang melekat  dengan  simpul  ke- 𝑣 𝑖 untu 1 ≤  𝑖 ≤  𝑚 . Konstruksi  pewarnaan  kromatik  dominasi 𝑓 ∶  𝑉(𝐻) → { 1, 2, 3, … 𝜒 𝑑 (𝐻)} terdapat  dua  kasus  :  kasus  I  ketika
𝐶 𝑛 .  memiliki  order  genap.  Kasus  II  ketika 𝐶 𝑛 memiliki order  gasal.  Kasus  I  untuk 𝑢 {𝑖(2𝑗+1)} katakan 𝑓(𝑢 {𝑖(2𝑗+1)} )   =  1 ,  untuk 𝑢 {𝑖(2𝑗)} katakan 𝑓(𝑢 {𝑖(2𝑗)} )   = 2 ,  dan  untuk  untuk 𝑣 𝑖 katakan 𝑓(𝑣 𝑖 )   =  2  +  𝑖 .  Untuk setiap 1 ≤  𝑖 ≤  𝑚, 0 ≤  𝑗 $  Maka  kita  telah  selesai dengan |𝑉(𝑃 𝑚 )|   + 2 warna.  Kasus  II  untuk 𝑢 {𝑖(2𝑗+1)} katakan 𝑓(𝑢 {𝑖(2𝑗+1)} )   =  1 ,  untuk 𝑢 {𝑖(2𝑗)} katakan 𝑓(𝑢 {𝑖(2𝑗)} )   =  2 ,untuk 𝑢 {𝑖𝑛} katakan 𝑓(𝑢 {𝑖𝑛} )   =  3 dan untuk  untuk 𝑣 𝑖 katakan 𝑓(𝑣 𝑖 )   =  3  +  𝑖 .  Kasus  II  ini menghasilkan  pewarnaan  kromatik  dominasi  karena setiap  simpul 𝑣 𝑖 mendominasi  dirinya  sendiri  dan mendominasi kelas warna  1,  2, dan 3. Sebaliknya  setiap kelas warna 1, 2, 3 mendominasi warna yang unik. Maka kita telah selesai dengan |𝑉(𝑃 𝑚 )|   +  3 warna. ∎
Bilangan  kromatik  dominasi  dari  graf  hasil  operasi korona  Lintasan  ( 𝑃 𝑚 )  dengan  Lingkaran  ( 𝐶 𝑛 )  ditentukan oleh  order  Lintasan  ( 𝑃 𝑚 )  sebab  Lingkaran  ( 𝐶 𝑛 )  minimal harus  diwarnai  dengan  2  atau  3  warna  sedangkan Lintasan ( 𝑃 𝑚 ) minimal harus diwarnai sebanyak 𝑚 warna agar memenuhi sifat kromatik dominasi minimum. Lebih jelasnya,  Perhatikan  Contoh  II.2.1  dan  Contoh  II.2.2 berikut ini.
Contoh II.2.1 Diberikan  Lintasan 𝑃 3 dan  Lingkaran 𝐶 4 ,  Jika  Graf 𝐻 1 = 𝑃 3 ⊙   𝐶 4 adalah graf hasil operasi korona Lintasan dan  Lingkaran,  maka  dengan  menggunakan  Observasi II.2  maka  didapatkan  bahwa 𝜒 𝑑 (𝐻 1 ) = 5 ,  sebagaimana yang ditunjukkan pada Gambar 3.
Gambar 3. Kromatik Dominasi 𝐻 1 Contoh II.2.2 Diberikan  Lintasan 𝑃 4 dan  Lingkaran 𝐶 5 ,  Jika  Graf 𝐻 2 = 𝑃 4 ⊙   𝐶 5 adalah graf hasil operasi korona Lintasan 𝑃 4 dan  Lingkaran 𝐶 5 ,  maka  dengan  menggunakan Observasi  II.2  maka  didapatkan  bahwa 𝜒 𝑑 (𝐻 2 ) = 7 , sebagaimana yang ditunjukkan pada Gambar 4
Kr o matik Dominasi Lingkaran dengan Lintasan.
Observasi  II.3 ( Kromatik  Dominasi 𝐶 𝑚 ⊙ 𝑃 𝑛 ) Diberikan  Lingkaran 𝐶 𝑚 dan  Lintasan 𝑃 𝑛 masing- masing memiliki order 𝑚 ≥ 4, 𝑛 ≥  2 , 𝑚, 𝑛 ∈   𝑁 . Jika 𝐼 adalah graf hasil operasi korona dari 𝐶 𝑚 dan 𝑃 𝑛 ,  maka bilangan kromatik dominasi dari 𝜒 𝑑 (𝐼) = |𝑉(𝐶 𝑚 )|   + 2.
Bukti. Misalkan Graf I adalah graf hasil korona dari graf 𝐶 𝑚 dan 𝑃 𝑛 ,  yaitu 𝐼 = 𝐶 𝑚 ⊙   𝑃 𝑛 .  Order  dari  Lingkaran |𝐶 𝑚 | = 𝑚 dan Lintasan |𝑃 𝑛 |   =  𝑛 . Katakan 𝑣 1 , 𝑣 2 , … , 𝑣 𝑚 adalah simpul-simpul graf 𝑃 𝑚 dan 𝑢 𝑖1 , 𝑢 𝑖2 , … , 𝑢 𝑖𝑛 adalah simpul-simpul 𝑃 𝑛 yang  melekat  dengan  simpul  ke- 𝑣 𝑖 untuk 1 ≤  𝑖 ≤  𝑚 .  Konstruksi  pewarnaan  kromatik dominasi 𝑓 ∶  𝑉(𝐼) →   { 1, 2, 3, … 𝜒 𝑑 (𝐼)} dengan menggunakan  | 𝑉(𝐶 𝑚 )|   + 2 warna  sebagai  berikut  : untuk 𝑢 𝑖(2𝑗+1) katakan 𝑓(𝑢 {𝑖(2𝑗+1)} ) =  1 ,  untuk 𝑢 𝑖(2𝑗) katakan 𝑓(𝑢 𝑖(2𝑗) ) =  2 kemudian  untuk 𝑣 𝑖 katakan 𝑓(𝑣 𝑖 )   =  2 + 𝑖 , untuk setiap 1 ≤  𝑖 ≤  𝑚, 0 ≤  𝑗 . Pewarnaan ini merupakan pewarnaan kromatik dominasi dari 𝐼 , karena pewarnaan ini tetap merupakan pewarnaan simpul  ( proper  coloring )  dan  himpunan  dominasi minimum  dari  graf 𝐼 mendominasi  setiap  simpul  dari kelas warna dengan kata lain simpul dengan kelas warna 1  dan  2  bertetangga  dengan  simpul  dengan  warna  yang unik.  Dengan  demikian,  didapatkan  bahwa 𝜒 𝑑 (𝐼)   = |𝑉(𝐶 𝑚 )|   +  2 .
Bilangan  kromatik  dominasi  dari  graf  hasil  operasi korona  Lingkaran  ( 𝐶 𝑚 )  dengan  Lintasan  ( 𝑃 𝑛 )  ditentukan oleh  order  Lingkaran  ( 𝐶 𝑚 )  sebab  Lintasan  ( 𝑃 𝑛 )  minimal harus  diwarnai  dengan  2  warna  sedangkan  Lingkaran ( 𝐶 𝑚 )  minimal  harus  diwarnai  sebanyak  m  warna  agar memenuhi  sifat  kromatik  dominasi  minimum.  Lebih jelasnya,  Perhatikan  Contoh  II.3.1.  dan  Contoh  II.3.2. berikut ini .
Contoh II.3.1 Diberikan  Lingkaran 𝐶 4 dan  Lintasan 𝑃 3 ,  Jika  Graf 𝐼 1 = 𝐶 4 ⊙   𝑃 3 adalah graf hasil operasi korona Lingkaran 𝐶 4 dan 𝑃 3 ,  maka  dengan  menggunakan  Observasi  II.3 maka  didapatkan  bahwa 𝜒 𝑑 (𝐼 1 ) = 6 ,  sebagaimana  yang ditunjukkan pada Gambar 5.
Gambar 5. Kromatik Dominasi 𝐼 1 Contoh II.3.2 Diberikan  Lingkaran 𝐶 5 dan  Lintasan 𝑃 4 ,  Jika  Graf 𝐼 2 = 𝐶 5 ⊙   𝑃 4 adalah graf hasil operasi korona Lingkaran 𝐶 5 dan 𝑃 4 ,  maka  dengan  menggunakan  Observasi  II.3 maka  didapatkan  bahwa 𝜒 𝑑 (𝐼 2 ) = 7 ,  sebagaimana  yang ditunjukkan pada Gambar 6.
Kromatik Dominasi Lingkaran dengan Lingkaran.
Observasi  II.4 ( Kromatik  Dominasi 𝐶 𝑚 ⊙ 𝐶 𝑛 ) Diberikan  Lingkaran 𝐶 𝑚 dan 𝐶 𝑛 masing-masing memiliki order 𝑚, 𝑛 ≥ 4, 𝑚, 𝑛 ∈   𝑁 . Jika J  adalah graf hasil  operasi  korona  dari 𝐶 𝑚 dan 𝐶 𝑛 ,    maka  bilangan kromatik dominasi dari 𝜒 𝑑 (𝐽)   =
{ |𝑉(𝐶 𝑚 )| + 2 , 𝑛 𝑔𝑒𝑛𝑎𝑝 |𝑉(𝐶 𝑚 )| + 3 , 𝑛 𝑔𝑎𝑠𝑎𝑙
Bukti. Misalkan Graf 𝐽 adalah graf hasil korona dari graf 𝐶 𝑚 dan 𝐶 𝑛 ,  yaitu    J = 𝐶 𝑚 ⊙   𝐶 𝑛 .  Order  dari  Lingkaran | 𝐶 𝑚 |   =  𝑚 dan  Lingkaran | 𝐶 𝑛 |   =  𝑛 .  Katakan 𝑣 1 , 𝑣 2 , … , 𝑣 𝑚 adalah  simpul-simpul  graf 𝐶 𝑚 dan 𝑢 {𝑖1} , 𝑢 {𝑖2} , … , 𝑢 {𝑖𝑛} adalah  simpul-simpul 𝐶 𝑛 yang melekat  dengan  simpul  ke- 𝑣 𝑖 untu 1 ≤  𝑖 ≤  𝑚 . Konstruksi  pewarnaan  kromatik  dominasi 𝑓 ∶  𝑉(𝐽) → { 1, 2, 3, … 𝜒 𝑑 (𝐽)} terdapat  dua  kasus  :  kasus  I  ketika 𝐶 𝑛 .  memiliki  order  genap.  Kasus  II  ketika 𝐶 𝑛 memiliki order  gasal.  Kasus  I  untuk 𝑢 {𝑖(2𝑗+1)} katakan 𝑓(𝑢 {𝑖(2𝑗+1)} )   =  1 ,  untuk 𝑢 {𝑖(2𝑗)} katakan 𝑓(𝑢 {𝑖(2𝑗)} )   = 2 ,  dan  untuk  untuk 𝑣 𝑖 katakan 𝑓(𝑣 𝑖 )   =  2  +  𝑖 .  Untuk setiap 1 ≤  𝑖 ≤  𝑚, 0 ≤  𝑗 $  Maka  kita  telah  selesai dengan |𝑉(𝐶 𝑚 )|   + 2 warna.  Kasus  II  untuk 𝑢 {𝑖(2𝑗+1)} katakan 𝑓(𝑢 {𝑖(2𝑗+1)} )   =  1 ,  untuk 𝑢 {𝑖(2𝑗)} katakan 𝑓(𝑢 {𝑖(2𝑗)} )   =  2 ,untuk 𝑢 {𝑖𝑛} katakan 𝑓(𝑢 {𝑖𝑛} )   =  3 dan untuk  untuk 𝑣 𝑖 katakan 𝑓(𝑣 𝑖 )   =  3  +  𝑖 .  Kasus  II  ini menghasilkan  pewarnaan  kromatik  dominasi  karena setiap  simpul 𝑣 𝑖 mendominasi  dirinya  sendiri  dan mendominasi kelas warna  1,  2, dan 3. Sebaliknya setiap kelas warna 1, 2, 3 mendominasi warna yang unik. Maka kita telah selesai dengan |𝑉(𝐶 𝑚 )|   +  3 warna. ∎
Bilangan  kromatik  dominasi  dari  graf  hasil  operasi korona  Lingkaran  ( 𝐶 𝑚 )  dengan  Lingkaran  ( 𝐶 𝑛 ) ditentukan  oleh  Lingkran  ( 𝐶 𝑚 )  sebab  Lingkaran  ( 𝐶 𝑛 ) minimal  harus  diwarnai  dengan  2  atau  3  warna sedangkan  Lingkaran  ( 𝐶 𝑚 )  minimal  harus  diwarnai sebanyak 𝑚 warna  agar  memenuhi  sifat  kromatik dominasi  minimum.  Lebih  jelasnya,  Perhatikan  Contoh II.4.1 dan Contoh II.4.2 berikut ini.
Contoh II.4.1 Diberikan Lingkaran 𝐶 5 dan 𝐶 4 , Jika Graf 𝐽 1 =   𝐶 5 ⊙ 𝐶 4 adalah  graf  hasil  operasi  korona  Lingkaran  dengan Lingkaran,  maka  dengan  menggunakan  Observasi  II.4 maka didapatkan bahwa 𝜒 𝑑 (𝐽 1 )   =  7 , sebagaimana yang ditunjukkan pada Gambar 8.

## Contoh II.4.2
Diberikan  Lingkaran 𝐶 6 dan 𝐶 5 ,  Graf 𝐽 2 = 𝐶 6 ⊙ 𝐶 5 adalah  graf  hasil  korona  Lintasan 𝐶 6 dan 𝐶 5 ,  maka dengan  menggunakan  Observasi  II.4  maka  didapatkan bahwa 𝜒 𝑑 (𝐽 2 )   =  9 , sebagaimana yang ditunjukkan pada Gambar 9
Gambar 9. Kromatik Dominasi 𝐽 2 Kromatik Dominasi Graf Lengkap dengan Lingkaran atau Lingkaran.
Observasi II.5. ( Kromatik Dominasi 𝐾 𝑚 ⊙ 𝑃 𝑛 ) Diberikan  graf  Lengkap 𝐾 𝑚 dan  Lintasan 𝑃 𝑛 masing- masing  memiliki  order 𝑚 ≥  1, 𝑛 ≥ 2, 𝑚, 𝑛 ∈  𝑁 .  Jika 𝐿 adalah  graf  hasil  operasi  korona  dari 𝐾 𝑚 dan 𝑃 𝑛 maka bilangan kromatik dominasi dari 𝑥 𝑑 (L) = |V(K m )| + 2 .
Bukti. Misalkan Graf I adalah graf hasil korona dari graf 𝐾 𝑚 dan 𝑃 𝑛 ,  yaitu 𝐿 = 𝐾 𝑚 ⊙   𝑃 𝑛 .  Order  dari  Lingkaran |𝐾 𝑚 | = 𝑚 dan Lintasan |𝑃 𝑛 |   =  𝑛 . Katakan 𝑣 1 , 𝑣 2 , … , 𝑣 𝑚 adalah simpul-simpul graf 𝐾 𝑚 dan 𝑢 𝑖1 , 𝑢 𝑖2 , … , 𝑢 𝑖𝑛 adalah simpul-simpul 𝑃 𝑛 yang  melekat  dengan  simpul  ke- 𝑣 𝑖 untuk 1 ≤  𝑖 ≤  𝑚 .  Konstruksi  pewarnaan  kromatik dominasi 𝑓 ∶  𝑉(𝐿) →   { 1, 2, 3, … 𝜒 𝑑 (𝐿)} dengan menggunakan  | 𝑉(𝐾 𝑚 )|   + 2 warna  sebagai  berikut  : untuk 𝑢 𝑖(2𝑗+1) katakan 𝑓(𝑢 {𝑖(2𝑗+1)} ) =  1 ,  untuk 𝑢 𝑖(2𝑗) katakan 𝑓(𝑢 𝑖(2𝑗) ) =  2 kemudian  untuk 𝑣 𝑖 katakan 𝑓(𝑣 𝑖 )   =  2 + 𝑖 , untuk setiap 1 ≤  𝑖 ≤  𝑚, 0 ≤  𝑗 . Pewarnaan ini merupakan pewarnaan kromatik dominasi dari 𝐼 , karena pewarnaan ini tetap merupakan pewarnaan simpul  ( proper  coloring )  dan  himpunan  dominasi minimum  dari  graf 𝐼 mendominasi  setiap  simpul  dari kelas warna dengan kata lain simpul dengan kelas warna 1  dan  2  bertetangga  dengan  simpul  dengan  warna  yang unik.  Dengan  demikian,  didapatkan  bahwa 𝜒 𝑑 (𝐿)   = |𝑉(𝐾 𝑚 )|   +  2 .
∎
Bilangan  kromatik  dominasi  dari  graf  hasil  operasi korona  graf  Lengkap  ( 𝐾 𝑚 )  dengan  Lintasan  ( 𝑃 𝑛 ) ditentukan oleh order graf Lengkap ( 𝐾 𝑚 ) sebab Lintasan ( 𝑃 𝑛 )  minimal  harus  diwarnai  dengan  2  warna sedangkan graf  Lengkap  ( 𝐾 𝑚 )  minimal  harus  diwarnai  sebanyak 𝑚 warna agar memenuhi sifat kromatik dominasi minimum. Lebih  jelasnya,  Perhatikan  Contoh  II.5.1  dan  Contoh II.5.2 berikut ini.
Contoh II.5.1 . Diberikan graf Lengkap 𝐾 4 dan Lintasan 𝑃 3 , Jika Graf 𝐿 1 =   𝐾 4 ⊙ 𝑃 3 adalah  graf  hasil  operasi  korona  graf Lengkap  dan  Lingkaran,  maka  dengan  menggunakan Observasi  II.5  maka  didapatkan  bahwa 𝜒 𝑑 (𝐿 1 )   =  6 , sebagaimana yang ditunjukkan pada Gambar 10.
Gambar 10. Kromatik dominasi 𝐿 1 .
Contoh II.5.2 Diberikan  graf  Lengkap 𝐾 5 dan  Lintasan 𝑃 4 Jika  Graf 𝐿 2 =   𝐾 5 ⊙ 𝑃 4 adalah  graf  hasil  operasi  korona  graf Lengkap  dan  Lingkaran,  maka  dengan  menggunakan Observasi  II.5  maka  didapatkan  bahwa 𝜒 𝑑 (𝐿 2 )   =  7 , sebagaimana yang ditunjukkan pada Gambar 11.
Gambar 11. Kromatik dominasi 𝐿 2 .
Observasi  II.6 ( Kromatik  Dominasi 𝐾 𝑚 ⊙ 𝐶 𝑛 ) Diberikan Graf lengkap 𝐾 𝑚 dan Lingkaran 𝐶 𝑛 masing- masing memiliki order 𝑚 ≥ 1, 𝑛 ≥ 4, 𝑚, 𝑛 ∈   𝑁 . Jika M adalah  graf  hasil  operasi  korona  dari 𝐾 𝑚 dan 𝐶 𝑛 , maka  bilangan  kromatik  dominasi  dari 𝜒 𝑑 (𝑀)   = { |𝑉(𝐾 𝑚 )| + 2 , 𝑛 𝑔𝑒𝑛𝑎𝑝 |𝑉(𝐾 𝑚 )| + 3 , 𝑛 𝑔𝑎𝑠𝑎𝑙
Bukti. Misalkan  Graf 𝑀 adalah  graf  hasil  korona  dari graf 𝐾 𝑚 dan 𝐶 𝑛 ,  yaitu    M = 𝐾 𝑚 ⊙   𝐶 𝑛 .  Order  dari  graf lengkap | 𝐾 𝑚 |   =  𝑚 dan  Lingkaran | 𝐶 𝑛 |   =  𝑛 . Katakan 𝑣 1 , 𝑣 2 , … , 𝑣 𝑚 adalah simpul-simpul graf 𝐾 𝑚 dan 𝑢 {𝑖1} , 𝑢 {𝑖2} , … , 𝑢 {𝑖𝑛} adalah  simpul-simpul 𝐶 𝑛 yang melekat  dengan  simpul  ke- 𝑣 𝑖 untu 1 ≤  𝑖 ≤  𝑚 . Konstruksi  pewarnaan  kromatik  dominasi 𝑓 ∶  𝑉(𝑀) → { 1, 2, 3, … 𝜒 𝑑 (𝑀)} terdapat  dua  kasus  :  kasus  I  ketika
𝐶 𝑛 .  memiliki  order  genap.  Kasus  II  ketika 𝐶 𝑛 memiliki order  gasal.  Kasus  I  untuk 𝑢 {𝑖(2𝑗+1)} katakan 𝑓(𝑢 {𝑖(2𝑗+1)} )   =  1 ,  untuk 𝑢 {𝑖(2𝑗)} katakan 𝑓(𝑢 {𝑖(2𝑗)} )   = 2 ,  dan  untuk  untuk 𝑣 𝑖 katakan 𝑓(𝑣 𝑖 )   =  2  +  𝑖 .  Untuk setiap 1 ≤  𝑖 ≤  𝑚, 0 ≤  𝑗 $  Maka  kita  telah  selesai dengan |𝑉(𝐶 𝑚 )|   + 2 warna.  Kasus  II  untuk 𝑢 {𝑖(2𝑗+1)} katakan 𝑓(𝑢 {𝑖(2𝑗+1)} )   =  1 ,  untuk 𝑢 {𝑖(2𝑗)} katakan 𝑓(𝑢 {𝑖(2𝑗)} )   =  2 ,untuk 𝑢 {𝑖𝑛} katakan 𝑓(𝑢 {𝑖𝑛} )   =  3 dan untuk  untuk 𝑣 𝑖 katakan 𝑓(𝑣 𝑖 )   =  3  +  𝑖 .  Kasus  II  ini menghasilkan  pewarnaan  kromatik  dominasi  karena setiap  simpul 𝑣 𝑖 mendominasi  dirinya  sendiri  dan mendominasi kelas warna 1, 2, dan 3. Sebaliknya setiap kelas warna 1, 2, 3 mendominasi warna yang unik. Maka kita telah selesai dengan |𝑉(𝐾 𝑚 )|   +  3 warna. ∎
Bilangan  kromatik  dominasi  dari  graf  hasil  operasi korona  graf  Lengkap  ( 𝐾 𝑚 )  dengan  Lingkaran  ( 𝐶 𝑛 ) ditentukan oleh graf Lengkap ( 𝐾 𝑚 ) sebab Lingkaran ( 𝐶 𝑛 ) minimal  harus  diwarnai  dengan  2  atau  3  warna sedangkan  graf  Lengkap  ( 𝐾 𝑚 )  minimal  harus  diwarnai sebanyak  m  warna  agar  memenuhi  sifat  kromatik dominasi  minimum.  Lebih  jelasnya,  Perhatikan  Contoh II.6.1 dan Contoh II.6.2 berikut ini.

## Contoh II.6.1
Diberikan  graf  Lengkap 𝐾 5 dan  Lingkaran 𝐶 4 ,  Jika Graf 𝑀 1 =   𝐾 5 ⊙  𝐶 4 adalah  graf  hasil  operasi  korona graf Lengkap dan Lingkaran, maka dengan menggunakan Observasi  II.6  maka  didapatkan  bahwa 𝜒 𝑑 (𝑀 1 )   =  7 , sebagaimana yang ditunjukkan pada Gambar 12.
Gambar 12. Kromatik Dominasi 𝑀 1

## Contoh II.6.2
Diberikan  graf  Lengkap 𝐾 5 dan  Lingkaran 𝐶 5 ,  Jika Graf 𝑀 2 =   𝐾 5 ⊙  𝐶 5 adalah  graf  hasil  operasi  korona graf Lengkap dan Lingkaran, maka dengan menggunakan Observasi  II.6  maka  didapatkan  bahwa  _d(M2)  =  8, sebagaimana yang ditunjukkan pada Gambar 13 .
Apabila  diperhatikan  Bilangan  kromatik  dominasi  dari 𝑃 𝑚 ⊙ 𝑃 𝑛 , 𝐶 𝑚 ⊙   𝑃 𝑛 dan 𝐾 𝑚 ⊙   𝑃 𝑛 ketiganya  memiliki kesamaan  bentuk,  perbedaan  nya  hanya  pada  graf pertama  saja  yakni 𝑃 𝑚 , 𝐶 𝑛 dan 𝐾 𝑚 ,  sehingga  dari  ketiga
bentuk yang sama tersebut dapat dituliskan bentuk umum dari  bilangan  kromatik  dominasi  dari  sebarang  graf terhubung  sederhana 𝐺 𝑚 dengan  Lintasan 𝑃 𝑛 sebagai berikut.
Teorema  II.1 . Diberikan  sebarang  graf  terhubung dengan order m ( G m ) dan  Lintasan  dengan  order n ( P n ) . Bilangan kromatik  dominasi χ d (G m ⊙ P n )   = |V (G m )| + 2 ,  untuk 𝑚 ≥ 1, 𝑛 ≥ 2 .
Demikian  pula  bentuk 𝑃 𝑚 ⊙   𝐶 𝑛 , 𝐶 𝑚 ⊙   𝐶 𝑛 dan 𝐾 𝑚 ⊙ 𝐶 𝑛 secara  umum  ialah  sama  yakni  untuk  n  ganjil ditambah 3 warna dan untuk n genap ditambah 2 warna, sedangkan Lingkaran 𝐶 𝑚 , Lintasan 𝑃 𝑚 dan graf Lengkap 𝐾 𝑚 diwarnai  dengan  m  warna,  sehingga  dari  ketiga bentuk yang sama tersebut dapat dituliskan bentuk umum dari  bilangan  kromatik  dominasi  dari  sebarang  graf terhubung  sederhana 𝐺 𝑚 dengan  Lingkaran 𝐶 𝑛 sebagai berikut.
Gambar 13 . Kromatik Dominasi 𝑀 2
Teorema  II.2.  Diberikan  Graf  lengkap 𝐺 𝑚 dan Lingkaran 𝐶 𝑛 masing-masing  memiliki  order 𝑚 ≥ 1, 𝑛 ≥ 4, 𝑚, 𝑛 ∈   𝑁 .  Jika  M  adalah  graf  hasil  operasi korona  dari 𝐺 𝑚 dan 𝐶 𝑛 ,    maka  bilangan  kromatik dominasi dari
𝜒 𝑑 (𝐺 𝑚 ⊙ 𝐶 𝑛 )   = { |𝑉(𝐺 𝑚 )| + 2 , 𝑛 𝑔𝑒𝑛𝑎𝑝 |𝑉(𝐺 𝑚 )| + 3 , 𝑛 𝑔𝑎𝑠𝑎𝑙

## III. KESIMPULAN
Berdasarkan  hasil  analisis  dan  pembahasan  pada bagian  sebelumnya,  dapat  disimpulkan  beberapa  hal berikut:
1. Diberikan  sebarang  graf  terhubung  dengan  order  m ( 𝐺 𝑚 )  dan  Lintasan  dengan  order  n  ( 𝑃 𝑛 ).  Bilangan kromatik dominasi 𝜒 𝑑 (𝐺 𝑚 ⊙   𝑃 𝑛 )   = |𝑉 (𝐺 𝑚 )|   +  2 , untuk 𝑚 ≥  1;  𝑛 ≥ 2 . 2. Diberikan  sebarang  graf  terhubung  dengan  order 𝑚 ( 𝐺 𝑚 )  dan  Lingkaran  dengan  order 𝑛 ( 𝐶 𝑛 ).  Bilangan kromatik dominasi 𝜒 𝑑 (𝐺 𝑚 ⊙   𝐶 𝑛 )   = |𝑉 (𝐺 𝑚 )|   +  2 , dan |𝑉 (𝐺 𝑚 )| + 3 , berturut-turut untuk 𝑛 genap, dan 𝑛 gasa l.

## UCAPAN TERIMA KASIH
Penulis  Muhammad  A.  Hadi  mengucapkan  terima kasih  kepada Direktorat Pendidikan  Tinggi,  Departemen Pendidikan  dan  Kebudayaan  Republik  Indonesia  yang telah  memberikan  dukungan  finansial  melalui  Beasiswa Bidik Misi tahun 2012- 2016.

## DAFTAR PUSTAKA
[1] N. Hartsfield and G. Ringel, Pearls in graph theory: a  comprehensive  introduction. Courier  Corporation, 2013.
[2] T.  W.  Haynes,  S.  Hedetniemi,  and  P.  Slater, Fundamentals of Domination in graphs . CRC Press, 1998.
[3] C.  E.  Go  and  S.  R.  Canoy  Jr,  “Domination  in  the corona  and  join  of  graphs,”  in International Mathematical Forum ,  vol. 6, no.  16, 2011, pp 763– 771.
[4] A.  Benjamin,  G.  Chartrand,  and  P.  Zhang, The Fascinating  World  of  Graph  Theory .  Princeton,  NJ, USA: Princeton University Press, 2015.
[5] R. Gera, C. Rasmussen, and S. Horton, “Dominator colorings  and  safe  clique  partitions,” Congressus numerantium , vol. 181, p. 19, 2006.
[6] S.  Arumugam,  J.  Bagga,  and  K.  R.  Chandrasekar, “On  dominator  colorings  in  graphs,” Proceedings- Mathematical Sciences , vol. 122, no. 4, pp. 561–571, 2012.
[7] R.  Gera,  “On  the  dominator  colorings  in  bipartite graphs,” in Information Technology, 2007. ITNG’07.
Fourth  International  Conference  on .  IEEE,  2007, pp. 947–952.