Pewarnaan Lokal Wilayah Super Antimagic Pada Graf Planar

Abstract

Konsep pewarnaan graf puncaknya muncul pada tahun 1976, yaitu sebagai hasil dari pemecahan persoalan 4 warna. Setelahnya muncul konsep pelabelan graf. Pada tahun 2017 Arumugam menggabungkan dua konsep tersebut, yaitu memperkenalkan konsep pewarnaan yang didapatkan dari bobot suatu pelabelan. Misalkan G = (V;E) adalah suatu graf terhubung dengan n titik dan m sisi. Fungsi bijektif f : E ¡! f1; 2; 3; :::;mg disebut pelabelan antimagic lokal jika untuk setiap dua titik yang bertetangga u dan v di G, w(u) 6= w(v), dengan w(u) = P e2E(u) f(e). Pelabelan antimagic lokal menginduksi pewarnaan titik pada graf G dimana titik v diberi warna atau bobot w(v). Termotivasi oleh penelitian Arumugam, pada tesis ini dikaji tentang pewarnaan lokal wilayah super antimagic pada graf planar. Misalkan G = (V;E) adalah suatu graf terhubung dengan n titik danmsisi. Fungsi bijektif f : V (G)[E(G) ¡! f1; 2; :::; n+ mg disebut pelabelan lokal wilayah super antimagic jika terdapat fungsi bijektif f : V (G) ! f1; 2; : : : ; ng dan fungsi bijektif f¤ : E(G) ! fn + 1; n + 2; : : : ; n + mg sedemikian sehingga untuk dua wilayah yang saling bertetangga A1 dan A2 di G, w(A1) 6= w(A2). Pelabelan lokal wilayah super antimagic menginduksi pewarnaan wilayah pada graf G dengan wilayah A diberi warna atau bobot w(A). Bilangan kromatik lokal wilayah super antimagic dinotasikan dengan °lfat(G), didefinisikan sebagai banyak warna terkecil dari seluruh warna pada G dari hasil proses beberapa pelabelan lokal wilayah super antimagic pada G. Pada penelitian ini diperoleh hubungan antara bilangan kromatik pewarnaan wilayah graf G dengan bilangan kromatik yang didapatkan dari proses pelabelan, yaitu bilangan kromatik lokal wilayah super antimagic. Pada graf terhubung, bilangan kromatik lokal wilayah super antimagic °lfat(G) = 1 diperoleh jika G merupakan graf yang memiliki satu wilayah berhingga. Selain itu diperoleh juga °lfat(G) ¸ 2 jika G merupakan graf yang memiliki lebih dari satu wilayah berhingga dan setidaknya terdapat dua wilayah yang saling bertetangga. Selanjutnya pewarnaan lokal wilayah super antimagic diterapkan pada beberapa graf planar yang telah direpresentasikan dalam bentuk graf bidang, yaitu graf kipas (Fn), graf roda (Wn), graf ladder (Ln), graf triangular ladder (TLn), dan graf three circular ladder (TCLn). Pada semua kelas graf yang telah disebutkan, kecuali graf three circular ladder dengan jumlah wilayah ganjil diperoleh keberbedaan bobot wilayah dari hasil pelabelannya sama dengan kromatik pewarnaan wilayahnya.