PEWARNAAN SIMPUL r-DINAMIS PADA GRAF TERATAI T_n

Abstract

G=(V,E) merupakan pasangan dari himpunan V tak kosong dan berhingga yang dinamakan sebagai himpunan simpul dan himpunan E yang seluruh elemennya merupakan subhimpunan dari dua elemen dari V atau bisa disebut juga dengan busur. Pewarnaan dinamis didefinisikan sebagai pewarnaan tepat sedemikian sehingga untuk setiap simpul berderajat minimal dua mempunyai lebih dari satu warna yang berbeda pada setiap simpul-simpul tetangga. Pewarnaan r-dinamis merupakan bentuk perumuman dari pewarnaan dinamis. Misalkan r merupakan bilangan bulat positif. Pewarnaan r-dinamis dengan k-warna pada suatu graf G adalah pewarnaan tepat simpul dengan k-warna pada graf G sedemikian sehingga untuk setiap simpul v maka himpunan tetangganya akan menggunakan warna setidaknya min⁡{r,deg⁡(v)}. nilai minimal k untuk graf G pada pewarnaan r-dinamis dengan k-warna disebut dengan bilangan kromatik r-dinamis pada graf G, dan dapat dinotasikan dengan χ_r (G). Graf teratai T_n merupakan hasil dari operasi korona antara graf lengkap K_1 dengan graf bintang S_n (K_1⊙S_n) yang kemudian n-1 simpul pada graf bintang digantikan menjadi n-1 simpul baru dan terhubung pada simpul pusat pada graf bintang. Sehingga, graf teratai akan memiliki 2n+2 simpul dan 2n+1 busur. Dari hasil konstruksi dengan menggunakan definisi pewarnaan r-dinamis pada graf teratai T_n, diperoleh bilangan kromatik graf teratai T_n adalah χ_r (T_n )=3, untuk r=1 dan 2, serta χ_r (T_n )=min⁡(r,2n+1)+1 untuk r≥3