BILANGAN KROMATIK LOKASI DARI GRAF ULAT

Abstract

Abstrak. Bilangan kromatik lokasi dari G adalah minimum dari banyaknya warna yang
digunakan pada pewarnaan lokasi dari graf G. Misalkan G = (V; E) adalah graf terhubung
dan c suatu pewarnaan dari G. Untuk 1 i k, kita defenisikan S
merupakan
himpunan dari titik yang diberi warna i. Kode warna c
(v) dari titik V merupakan
vektor dengan banyak unsur k yaitu (d(v; S
1
); d(v; S
2

); ; d(v; S
k
i
)), dimana d(v; S
)
adalah jarak dari v ke S
. Jika setiap titik yang berbeda di G memiliki kode warna yang
berbeda untuk suatu , maka c disebut pewarnaan lokasi dari G. Graf Ulat adalah graf
yang jika semua titik ujungnya dihilangkan akan menghasilkan lintasan [6]. Graf ulat
didapatkan dengan menghubungkan titik pusat c dari subgraf bintang secara berurutan.
Lintasan yang menghubungkan titik-titik daun dari barisan graf bintang disebut titik
backbone dari graf ulat. Jika banyaknya titik daun sama maka graf tersebut merupakan
graf ulat teratur, dinotasikan dengan C
i
dengan m adalah jumlah titik simpul dan
n adalah jumlah titik daun. Pada tulisan ini, akan dikaji kembali disertasi [1] tentang
bilangan kromatik lokasi dari graf ulat.