Pewarnaan Lokal Sisi Antimagic pada Keluarga Graf Pohon dan Graf Hasil Operasi Shackle

Abstract

Pelabelan dan pewarnaan graf merupakan kajian teori graf. Pelabelan graf G adalah sebuah pemetaan yang memetakan elemen-elemen graf G ke bilangan (biasanya bilangan bulat positif) dengan suatu aturan tertentu. Pelabelan graf berdasarkan domain pemetaannya terdiri dari pelabelan titik (vertex labeling), pelabelan sisi (edge labeling), dan pelabelan total (total labeling). Penjumlahan dari label yang terdapat pada titik dan sisi dari suatu graf disebut bobot. Jika pelabelan menghasilkan bobot titik atau bobot sisi yang berbeda disebut pelabelan antimagic. Pelabelan antimagic ini diperkenalkan oleh Hartsfield dan Ringel pada tahun 1990-an. Pewarnaan graf terdiri dari tiga jenis yaitu pewarnaan titik (vertex coloring), pewarnaan sisi (edge coloring), dan pewarnaan wilayah (region coloring). Pewarnaan titik pada graf G adalah pemberian warna pada titik-titik graf G, satu warna untuk setiap titik, sedemikian hingga titik-titik yang bertetangga diwarnai dengan warna berbeda. Pewarnaan sisi pada graf G adalah pemberian warna pada sisi-sisi graf G, satu warna untuk setiap sisi, sedemikian hingga sisi-sisi yang bertetangga diwarnai dengan warna berbeda. Banyaknya minimum warna yang digunakan untuk pewarnaan sisi pada graf G disebut sebagai bilangan kromatik sisi graf G dan dinotasikan dengan γ0 (G). Pewarnaan wilayah pada graf G adalah pemberian warna pada setiap wilayah pada graf G sehingga wilayah bertetangga tidak memiliki warna yang sama. Penelitian tentang pewarnaan graf yang saat ini baru berkembang yaitu pewarnaan lokal sisi antimagic yang dikemukakan oleh Agustin et al (2017). Pewarnaan lokal sisi antimagic dapat didefinsikan sebagai berikut, sebuah bijeksi f: V (g) → {1, 2, 3, ..., |V(G)|} disebut pelabelan lokal sisi antimagic untuk dua sisi yang betetangga e1 dan e2 , w(e1 ) = w(e2 ), dimana e = uv ∈ G, w(e) = f (u) + f (v). Dengan demikian, setiap pelabelan lokal sisi antimagic merupakan pewarnaan sisi pada graf G jika setiap sisi e ditentukan warna w(e). Banyak warna yang minimum untuk mewarnai pada pelabelan lokal sisi antimagic pada graf G disebut dengan bilangan kromatik lokal sisi antimagic yang dapat dinotasikan dengan γlea (G). Pewarnaan lokal sisi antimagic diterapkan pada keluarga graf pohon dan graf hasil operasi shackle. Adapun graf yang digunakan pada penelitian ini adalah graf bintang ganda (Double Star Graph), graf pohon pisang (banana tree graph), graf ulat teratur (caterpilar graph), graf kembang api (firecracker graph), dan graf bintang (star graph). Penelitian ini menggunakan metode deduktif dan pendeteksian pola. Pada penelitian ini dihasilkan 5 teorema baru yaitu bilangan kromatik pewarnaan lokal sisi antimagic pada graf bintang ganda (Sn,n ), graf pohon pisang (B2,n ), graf ulat teratur (Cn,m ), graf kembang api (Fn,m ), dan shackle graf bintang (shack(Sn , v, m)).