PEWARNAAN k-DIFERENSIAL DAN LINTASAN (k-1)-HAMILTON PADA GRAF

Abstract

Pewarnaan k-diferensial  merupakan generalisasi dari konsep pewarnaan graf, yang mengacu pada pemberian warna pada simpul sedemikian sehingga dua simpul yang bertetangga mempunyai perbedaan warna yang cukup kontras.  Secara sistematis  pewarnaan  k-diferensial adalah suatu pemetaan bijektif    sedemikian sehingga selisih mutlak antara label simpul yang saling bertetangga lebih besar atau sama dengan  k, yang kemudian diperoleh bilangan kromatik diferensial (dc(G))    Penelitian ini mengkaji mengenai pewarnaan  k-diferensial pada graf, menganalisis dan menentukan bilangan kromatik diferensial pada graf (dc(G)), dan menentukan keterkaitan dari masalah pewarnaan  k-differensial dengan lintasan (k-1)-Hamilton.  Lintasan Hamilton adalah pemetaan bijektif    sedemikian sehingga    sedangkan lintasan (k-1)-Hamilton merupakan lintasan Hamilton p  sedemikian sehingga jika  untuk setiap        maka  . Hasil penelitian menunjukkan bahwa pewarnaan  -diferensial pada    dapat menginduksi Lintasan (  k-1)-Hamilton pada  , sehingga  bahwa    permasalahan pewarnaan k-diferensial pada    identik dengan  pembentukan lintasan (k-1  )-Hamilton pada G^c.

Kata Kunci:  bijektif, pelabelan, bilangan kromatik diferensial