Perpustakaan Digital ITB

Teori pelabelan graf merupakan salah satu topik penting dalam teori graf yang mengkaji keseimbangan struktur graf melalui pemberian label pada titik dan sisi. Salah satu konsep awalnya adalah pelabelan kordial yang diperkenalkan oleh Cahit, yang kemudian dikembangkan oleh Lee dan Zhang melalui pelabelan persahabatan dan indeks persahabatan, di mana keseimbangan disyaratkan pada label titik, sedangkan ketidakseimbangan label sisi diukur menggunakan suatu indeks numerik. Secara formal, misalkan G adalah graf sederhana dengan himpunan titik V (G) dan himpunan sisi E(G). Suatu pelabelan titik f : V (G) ? Z2 menginduksi pelabelan sisi f? : E(G) ? Z2 yang didefinisikan oleh f?(uv) = |f(u) ? f(v)| untuk setiap uv ? E(G). Pelabelan f disebut pelabelan persahabatan apabila selisih banyaknya titik berlabel 0 dan 1 paling banyak satu. Pada pelabelan persahabatan f, indeks persahabatan didefinisikan sebagai FI(f) = |e0(f) ? e1(f)|, dengan ei(f) menyatakan banyaknya sisi berlabel i. Himpunan semua nilai FI(f) pada graf G dinotasikan dengan FI(G). Penelitian ini berfokus pada kajian indeks persahabatan dari graf barbel. Graf barbel B(G,H) dibentuk dengan menghubungkan dua graf terhubung melalui tepat satu sisi penghubung. Struktur ini menarik karena nilai indeks persahabatan sangat dipengaruhi oleh interaksi pelabelan pada graf penyusunnya dan label sisi penghubung. Tujuan tesis ini adalah menentukan himpunan indeks persahabatan dari graf barbel, khususnya ketika salah satu atau kedua graf penyusunnya merupakan graf bintang. Kajian difokuskan pada hubungan antara indeks persahabatan graf barbel dan graf penyusunnya, serta pengaruh paritas jumlah titik dan struktur graf terhadap nilai indeks yang dihasilkan. Hasil penelitian ini diharapkan dapat berkontribusi pada pengembangan teori pelabelan graf dan menjadi dasar bagi penelitian lanjutan pada graf hasil operasi lainnya.