## Polinomial Kromatik Graf Bunga
Risang Narendra 1
1 Universitas Nahdlatul Ulama Blitar, risang.narendra@gmail.com
Abstract. In  this  study,  the  class  of  a  graph  called  Flower  Graph  was  discussed. Flower Graph is a special way in a graphic. A graph G is called a flower chart- (𝑛 × 𝑚) . This graph will be symbolized by 𝑓 𝑛×𝑚 . Then, it is defined by a flower chart- (𝑛 × 𝑚) , with the petal to which 𝑖 in a flower graph- (𝑛 × 𝑚) , by (𝑛 − 1) -petal removed, for 𝑖 ∈ {1,2, ⋯ , 𝑛} . Flower graphics- (𝑛 × 𝑚) : with petal as much as 𝑖 is denoted by 𝑓 𝑛×𝑚 𝑖 .
Chromatic polynomial 𝜒(𝐺, 𝜆) is the amount of forms to color the point in graph G with 𝜆 color, where there are no two points that fit to obtain the same color. In the end, using the reduction theorem, the chromatic polynomial theorem of the Sikel chart and the chromatic polynomial graphic of the chromatic polynomial tree of a flower chart obtained.
Keywords: Chromatic polynomial, flower graph.
Abstrak. Dalam penelitian ini, dibahas kelas suatu graf yang dinamakan graf bunga. Graf  bunga  adalah  bentuk  khusus  dalam  suatu  graf.  Suatu  graf  G  dinamakan  graf bunga- (𝑛 × 𝑚) . Graf ini akan dilambangkan dengan 𝑓 𝑛×𝑚 . Kemudian, didefinisikan suatu  graf  bunga- (𝑛 × 𝑚) dengan kelopak sebanyak  i  menjadi graf bunga- (𝑛 × 𝑚) dengan (𝑛 − 1) -kelopak  dihapus,  untuk 𝑖 ∈ {1,2, ⋯ , 𝑛} .  Graf    bunga- (𝑛 × 𝑚) dengan kelopak sebanyak i dinotasikan dengan 𝑓 𝑛×𝑚 𝑖 . Polinomial kromatik 𝜒(𝐺, 𝜆) adalah banyaknya cara untuk mewarnai titik pada graf G  dengan 𝜆 warna,  dimana  tidak  ada  dua  titik  yang  adjasen  mendapat  warna  yang sama.    Pada  akhirnya,  dengan  menggunakan  teorema  reduksi , teorema  polinomial kromatik graf sikel, dan polinomial kromatik graf pohon polinomial kromatik suatu graf bunga didapatkan.
Kata Kunci: Polinomial kromatik, graf bunga

## 1  Pendahuluan
Teori  graf  merupakan  salah  satu  ilmu  yang  dibahas  dalam  matematika  yang mempelajari  himpunan  titik  dan  himpunan  garis.  Suatu  graf  merupakan  diagram yang  terdiri  dari  noktah-noktah  tidak  kosong  yang  disebut  titik  ( vertex )  dan dihubungkan oleh garis yang disebut sisi ( edge ).
Ada  beberapa  polinomial  yang  berhubungan  dengan  graf.  Polinomial memainkan  aturan  penting  dalam  mempelajari  graf  yang  merepresentasikan berbagai informasi tentang graf misalkan banyaknya pohon pada G dan banyaknya k-flow  tak  kosong  di  G.  Generalisasi  suatu  polinomial  graf  untuk  kelas  yang spesifik akan ditunjukkan pada penelitian ini.
Polinomial kromatik dari graf G, 𝜒(𝐺, 𝜆) menyatakan banyaknya cara mewarnai titik  pada  suatu  graf  dengan 𝜆 warna.  Dalam  penelitian  ini  dipelajari  suatu  graf khusus bernama graf bunga lengkap. Dimulai dengan mendefinisikan suatu graf

## Unisda Journal of Mathematics and Computer Science
bernama bunga lengkap- 𝑛 × 𝑚 . Dengan teorema reduksi, 𝜒(𝐺, 𝜆) = 𝜒(𝐺 − 𝑒, 𝜆) − 𝜒(𝐺 ∗ 𝑒, 𝜆) didapatkan  pernyataan  eksplisit  dari  polinomial  kromatik  dari  bunga lengkap- 𝑛 × 𝑚 dan beberapa subgraf dari bunga lengkap- 𝑛 × 𝑚 .

## 2 Graf Bunga
Pada bagian ini diberikan definisi dan suatu contoh dari suatu graf bunga. Suatu  graf  G  dinamakan  graf  bunga- (𝑛 × 𝑚) jika  graf  tersebut  memiliki himpunan  titik  sebagai  berikut: 𝑉(𝐺) = {1,2, ⋯ , 𝑛, 𝑛 + 1, ⋯ , 𝑛(𝑚 − 1)} dan himpunan  sisi 𝐸(𝐺) = {(1,2), (2,3), ⋯ , (𝑛 − 1, 𝑛), (𝑛, 1)}   ∪   {(1, 𝑛 + 1), (𝑛 + 1, 𝑛 + 2), (𝑛 + 2, 𝑛 + 3), (𝑛 + 3, 𝑛 + 4) ⋯ (𝑛 + 𝑚 − 3, 𝑛 + 𝑚 − 2), (𝑛 + 𝑚  − 2,2)}   ∪ {(2, 𝑛 + 𝑚 − 1), (𝑛 + 𝑚 − 1, 𝑛 + 𝑚), (𝑛 + 𝑚, 𝑛 + 𝑚 + 1), (𝑛 + 𝑚 + 1, 𝑛 + 𝑚 + 2), ⋯ , (𝑛 + 2(𝑚 − 2) − 1, 𝑛 + 2(𝑚 − 2)), (𝑛 + 2(𝑚 − 2), 3)} ∪ ⋯ ⋯ ⋯ ∪ {(𝑛, 𝑛 + (𝑛 − 1)(𝑚 − 2) + 1), (𝑛 + (𝑛 − 1)(𝑚 − 2) + 1, 𝑛 + (𝑛 − 1)(𝑚 − 2) + 2), (𝑛 + (𝑛 − 1)(𝑚 − 2) + 3), (𝑛 + (𝑛 − 1)(𝑚 − 2) + 3, 𝑛 + (𝑛 − 1)(𝑚 − 2) + 4), ⋯ , (𝑛𝑚 − 1, 𝑛𝑚), (𝑛𝑚, 1)} . Dengan kata lain, suatu graf G dinamakan graf bunga- (𝑛 × 𝑚) jika graf tersebut memiliki  n  titik  yang  membentuk  n-sikel  dan  n  himpunan  dari 𝑚 − 2 titik  yang membentuk m-sikel di sekitar n-sikel sehingga setiap m-sikel tepat satu memotong n-sikel pada satu sisi. Graf ini akan dilambangkan dengan 𝑓 𝑛×𝑚 . Jelas bahwa 𝑓 𝑛×𝑚 memiliki 𝑛(𝑚 − 1) titik  dan 𝑛𝑚 sisi.  m-sikel  dinamakan  kelopak  dan  n-sikel dinamakan pusat dari 𝑓 𝑛×𝑚 . n titik yang membentuk pusat memiliki derajat 4 dan semua titik lain yang memiliki derajat 2. Diagram pada Gambar 1 adalah contoh dari graf bunga
Gambar 1. Contoh Graf Bunga
Menghapus  sebuah  kelopak  dari 𝑓 𝑛𝑥𝑚 adalah  dengan  mengambil  satu  m-sikel dan  menghapus  semua  titik  berderajat  2  dan  sisi  yang  besesuaian.  Didefinisikan suatu graf bunga-(n x m) dengan i kelopak sebagai graf bunga-(n x m) dengan n kelopak  dihapus  untuk 𝑖 ∈ {1, 2, 3, … , 𝑛} .  Graf  bunga-(n  x  m)  dengan  i  kelopak dinotasikan  dengan 𝑓 𝑛𝑥𝑚 𝑖 .  Dengan  demikian  kita  memiliki  beberapa  graf  non- isomorfik  yang  direpresentasikan  sebagai 𝑓 𝑛𝑥𝑚 𝑖 .  Diagram  yang  ditunjukkan  pada gambar 2 adalah dua graf non-isomorfik yang direpresentasikan oleh 𝑓 7𝑥5 3 .
Gambar 2. Graf bunga-(7 x 5) dengan 3 kelopak

## Unisda Journal of Mathematics and Computer Science

## 3 Polinomial Kromatik
Pada  bagian  ini,  dijelaskan  tentang  pernyataan  eksplisit  polinomial kromatik  graf  bunga.  Sebelum  masuk  pada  polinomial  kromatik  graf  bunga, diberikan  teorema-teorema  penunjang.  Pembuktian  teorema  reduksi,  teorema polinomial kromatik graf pohon dan graf sikel mengacu pada [4] dan [5].
Teorema 3.1 (Reduksi). Jika ∈ 𝐸(𝐺) ,  maka 𝜒(𝐺, 𝜆) = 𝜒(𝐺 − 𝑒, 𝜆) − 𝜒(𝐺 ∗ 𝑒, 𝜆) ,
Teorema 3.2 Jika 𝑡 𝑛 adalah pohon dengan n titik, maka, 𝜒(𝑡 𝑛 , 𝜆) = 𝜆(𝜆 − 1) 𝑛−1
Teorema 3.3 Jika 𝐶 𝑛 adalah sikel-n maka
𝜒(𝐶 𝑛 , 𝜆) = (λ − 1) 𝑛 + (−1) 𝑛 (λ − 1) Untuk, 𝑛 > 2, 𝑛 ∈ ℕ
Pada akhirnya, dengan menerapkan teorema 3.1, teorema 3.2, dan teorema 3.3, didapatkan polinomial kromatik dari graf bunga.
Teorema  3.4 Misalkan  G  suatu  graf  dari  suatu  bunga  lengkap-(n  x  m).  Maka polinomial kromatik dari graf G adalah :
χ(𝐺, λ) = [ ∑ (−1) 𝑘 (λ − 1) 𝑚−𝑘−2 𝑚−2
𝑘=0 ] 𝑛 [(λ − 1) 𝑛 + (−1) 𝑛 (λ − 1)]
Akibat 3.5 Misalkan G graf dari suatu graf bunga-(n x m) dengan i kelopak, untuk 𝑖 = {1,2, ⋯ , 𝑛} maka
𝜒(𝐺, 𝜆) = [ ∑ (−1) 𝑘 (λ − 1) 𝑚−𝑘−2 𝑚−2 𝑘=0 ] 𝑖 [(λ − 1) 𝑛 + (−1) 𝑛 (𝜆  −  1)]

## 4 Kesimpulan
Hal  ini  ditunjukkan  sebelumnya  bahwa 𝑓 𝑛×𝑚 𝑖 untuk = {1,2, ⋯ 𝑛 − 1} mewakili graf bunga dengan i petal, dan kedudukan petal yang hilang adalah tidak relevan.  Jadi  didapatkan  graf  non-isomorfik  direpresentasikan  oleh 𝑓 𝑛×𝑚 𝑖 .  Jelas bahwa semua polinomial kromatik graf non-isomorfik direpresentasikan oleh 𝑓 𝑛×𝑚 𝑖 didapatkan.

## 5 Daftar Pustaka
[1]  Budayasa,  ketut.  2007.  Teori  graph  dan  aplikasinya.  Surabaya  :  unesa university press Surabaya.
[2]  Budayasa, ketut. 2008. Matematika Diskrit. Surabaya : unesa  university press Surabaya.
[3]  Johnsonbaugh, Richard. 2007. Matematika diskrit. Surabaya: PT.Prenhallindo

## Unisda Journal of Mathematics and Computer Science
[4]  Duval,  Art.  2005.  An  Example  of  Induction:  Chromatic  Polynomials. http://www.math.utep.edu/Faculty/duval/class/2325/084/chrpoly.pdf,  diakses Selasa, 3 Juli 2012, pukul 06.21 WIB)
[5]  Mphako-Banda,  Eunice.  2007.  Some  Polynomials  of  Flower  Graphs http://www.m-hikari.com/imf-password2007/49-52-2007/bandaIMF49-52- 2007.pdf diakses Selasa, 3 Juli 2012, pukul 17.39 WIB)