PELABELAN EDGE GRACEFUL PADA BEBERAPA KELAS GRAF

Abstract

Misal G graf dengan p titik dan q sisi. Pelabelan edge graceful pada graf G adalah pemberian nilai pada sisinya dengan bilangan bulat positif {1, 2, 3, ..., q} sedemikian hingga titiknya mendapat label dari penjumlahan label sisi yang menempel pada titik tersebut dalam modulo p yang berbeda semua, yaitu ( ) ( ) ( ) puvfvf ∑ Euv ∈ mod = untuk setiap Vv ∈ . Dengan demikian pelabelan titiknya memenuhi sifat bijektif dari himpunan V(G) ke himpunan bilangan bulat tak negatif {0, 1, 2, ..., p-1}. Syarat perlu dari suatu graf G dengan p titik dan q sisi memenuhi pelabelan edge graceful adalah

vii   ( ) ( ) ( ) pqq pp 1  .

Sebuah graf G  +≡   mod1 2 dikatakan edge graceful jika setiap sisi dan titik pada graf G dapat diberi label menurut aturan edge graceful. Permasalahan yang dibahas adalah menentukan apakah graf lengkap K , graf matahari M n , graf double star DS n , graf kipas F n , graf buku B n , graf friendship f , graf bipartit lengkap K m,n , graf bunga matahari (sunflower) SF , serta gabungan dari graf sikel dan graf lintasan ( PC n 3 n ∪ ) memenuhi syarat perlu pelabelan edge graceful atau tidak. Jika memenuhi syarat perlu pelabelan edge graceful, menyelidiki apakah kelaskelas

graf tersebut merupakan graf edge graceful atau tidak dengan cara melabeli kelas-kelas graf tersebut dengan aturan pelabelan edge graceful. Langkah-langkah untuk menyelesaikan permasalahan diatas sebagai berikut. Langkah pertama, yaitu selidiki apakah graf G dengan p titik dan q sisi memenuhi syarat perlu pelabelan edge graceful. Jika ya maka lanjutkan ke langkah kedua, tetapi jika tidak maka graf G tersebut tidak edge graceful