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 ( ) ( ) ( ) 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.