PELABELAN CORDIAL PADA BEBERAPA KELAS GRAF POHON

Abstract

Pelabelan cordial pada graf G merupakan pemberian label pada titik-titiknya dengan 0 dan 1 sehingga sisinya mendapat label harga mutlak dari selisih pelabelan titik-titik yang menempel pada sisinya, yang mempunyai sifat bahwa jumlah titik dan sisi yang berlabel 0 dan 1 berbeda paling banyak satu. Sebuah graf G dikatakan cordial jika dapat dilabeli menurut aturan pelabelan cordial. Penulisan skripsi ini bertujuan untuk mendapatkan perumusan pelabelan cordial pada graf superstar untuk setiap m dan n=2, graf centipede c untuk setiap n, graf double star DS untuk setiap n, graf banana tree B nm , n untuk setiap m dan n serta graf firecracker untuk setiap n dan m, jika graf tersebut dapat dilabeli secara cordial. Langkah-langkah penyelesaian dalam melabeli suatu graf G dengan pelabelan cordial adalah mendefinisikan titik-titik pada graf G dengan label 0 dan 1. Apabila jumlah titik graf G genap maka label 0 dan 1 berjumlah sama namun jika berjumlah ganjil maka label 0 dan 1 mempunyai selisih satu. Selanjutnya jika u dan v adalah titik-titik yang menempel pada sisi e maka untuk label sisinya diperoleh dari rumus

berselisih satu maka graf G dapat dilabeli secara cordial. Akan tetapi apabila selisih jumlah sisi yang berlabel 0 dan 1 lebih dari satu maka graf G tidak dapat dilabeli secara cordial, untuk itu labeli kembali titiknya dengan label 0 dan 1 di titik yang berbeda sampai diperoleh jumlah sisi yang berlabel 0 dan 1 dengan selisih paling banyak satu. Jika tidak bisa diperoleh jumlah sisi yang berlabel 0 dan 1 berbeda paling banyak satu, maka G tidak bisa dilabeli secara cordial. Dari penelitian yang telah dilakukan, diperoleh kesimpulan bahwa graf superstar S untuk setiap m, graf centipede c untuk setiap n, graf double star DS untuk setiap n, serta graf banana tree B n untuk setiap m dan n adalah graf cordial. Kemudian pada graf firecracker f nm , nm , untuk setiap m dan