PELABELAN EDGE GRACEFUL PADA BEBERAPA GRAF TERHUBUNG

Abstract

Misal graf G 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

  untuk setiap Vv  . Dengan demikian pelabelan titiknya  Euv mod memenuhi sifat bijektif dari himpunan V pelabelan edge graceful adalah

      pp mod1 2 1 vii   . Sebuah graf G dikatakan edge graceful jika setiap sisi dan titik pada graf G dapat diberi label menurut aturan edge graceful. Tujuan yang ingin dicapai adalah mengetahui apakah graf roda superstar S , graf dragon 3,m D , graf grid 3, n P P , dan graf kincir angin 4 n merupakan graf edge graceful. Merumuskan pelabelan edge graceful secara umum pada kelas-kelas graf tersebut jika kelas-kelas graf tersebut merupakan graf edge graceful. Langkah-langkah untuk mencapai tujuan diatas sebagai berikut. Langkah pertama, menyelidiki syarat perlu pelabelan edge graceful pada graf G dengan p titik dan q sisi. Jika memenuhi maka melanjutkan ke langkah kedua. Akan tetapi, jika syarat perlu pelabelan edge graceful tidak terpenuhi maka graf G tersebut bukan graf W , graf n K

edge graceful. Langkah kedua, memberi label setiap sisi pada graf G dengan himpunan bilangan bulat positif 1, 2, 3, ..., q yang berbeda semua. Langkah ketiga, memberi label pada setiap titik dengan cara menjumlahkan label sisi yang menempel pada titik tersebut, yaitu

  untuk setiap Vv  . Langkah  Euv viii mod keempat, menyelidiki label titiknya, jika berbeda semua yaitu memenuhi sifat bijektif dari himpunan titik V Hasil dari penelitian ini adalah sebagai berikut. Kelas graf yang tidak memenuhi syarat perlu pelabelan edge graceful yaitu graf roda W untuk 3n , graf grid PP  4 n untuk 4,3n , graf superstar untuk n genap, dan graf kincir angin

3,m n S untuk m ganjil, graf dragon K untuk setiap m dan n. Dengan demikian kelas-kelas graf tersebut bukan graf edge graceful. Kelas graf yang merupakan graf edge graceful yaitu graf roda S untuk m genap, dan graf dragon 3,m W , graf grid 3 D ,3 n PP  4 n untuk n ganjil. untuk 4,3n , graf