Perpustakaan Digital ITB

Perkembangan teori pelabelan graf dimulai dengan konsep ?-valuation yang diperkenalkan oleh (Rosa, 1967), yang kemudian dipopulerkan oleh (Golomb, 1972) dengan sebutan pelabelan anggun (graceful labeling). Evolusi konsep ini melahirkan pelabelan harmoni (harmonious labeling) (Graham dan Sloane, 1980a) dan pelabelan Kordial (cordial labeling) (Cahit, 1987). Kemudian (Lee dan Ng, 2008) memperkenalkan konsep indeks persahabatan (friendly index) sebagai generalisasi kuantitatif dari pelabelan kordial. Secara formal, indeks persahabatan dari suatu graf G didefinisikan sebagai himpunan FI(G) = {N(f) : f pelabelan persahabatan}, dengan N(f) = |ef (1) ? ef (0)| mengukur selisih jumlah sisi berlabel 1 dan 0 dari pelabelan persahabatan f : V (G) ? {0, 1}. Meskipun penelitian tentang indeks persahabatan telah berkembang cukup pesat, kajian literatur menunjukkan adanya dua celah penelitian (research gaps), yaitu pengaruh operasi graf terhadap indeks persahabatan dan karakterisasi graf berdasarkan kardinalitas indeks persahabatan. Dalam tesis ini akan dibahas indeks persahabatan untuk operasi tambah G+H, yang menghubungkan setiap titik di G dengan setiap titik di H. Pembahasan ini dibentuk dari sifat-sifat FI(G+H) terhadap pelabelan G dan H yang terinduksi. Kemudian penelitian ini juga akan membahas karakterisasi graf G yang memiliki kardinalitas indeks persahabatan kecil, yaitu |FI(G)| = 1 atau |FI(G)| = 2 dengan menentukan hubungan pertukaran label titik -titik di G terhadap indeks dari pelabelan persahabatan G.