Perpustakaan Digital ITB

Pelabelan total sisi-ajaib pada suatu graf dengan p titik dan q sisi adalah suatu pemetaan satu-satu yang memetakan semua titik dan sisi ke {1, 2, 3, p + q} dengan sifat bahwa untuk setiap sisi pada graf tersebut jumlah label sisi dan label kedua titik ujungnya sama. Sejak diperkenalkan oleh Kotzig dan Rosa pada tahun 1970, pelabelan ini telah dikaji oleh banyak peneliti. Misalnya, Enomoto, Llado, Nakamigawa dan Ringel mengkaji pelabelan ini dengan memperkenalkan istilah pelabelan total sisi-ajaib super, yaitu pelabelan total sisi-ajaib yang mempunyai sifat bahwa semua titik mendapat p label terkecil. Di samping itu perluasan dan variasi dari pelabelan ini telah diperkenalkan. Aplikasinya pun mulai dikaji, seperti aplikasi dalam kriptografi yang menggunakan pelabelan total sisi-ajaib dalam konstruksi skema pembagian rahasia. Studi mengenai pelabelan total sisi-ajaib (super) yang banyak mendapat perhatian adalah klasifikasi graf yang memiliki pelabelan tersebut. Beberapa kelas graf telah diketahui mempunyai pelabelan tersebut. Namun banyak permasalahan yang sampai kini belum terpecahkan. Di antaranya adalah konjektur yang menyatakan bahwa semua graf pohon memiliki pelabelan total sisi-ajaib (super). Termotivasi oleh konjektur tersebut beberapa peneliti mengkaji pelabelan ini secara khusus pada graf pohon. Selain itu, beberapa kelas graf juga sudah dibuktikan tidak mempunyai kedua pelabelan tersebut. Berkaitan dengan hal tersebut diperkenalkan konsep defisiensi sisi-ajaib (super) dari suatu graf. Konsep ini menyatakan seberapa dekat suatu graf dengan suatu graf yang mempunyai pelabelan total sisi-ajaib (super). Disertasi ini mengkaji dua permasalahan yaitu studi klasifikasi graf yang mempunyai pelabelan total sisi-ajaib (super) dan studi penentuan defisiensi total sisiajaib (super) dari beberapa kelas graf. Untuk masalah pertama, kami mengkaji ketotalsisiajaiban beberapa graf, yakni pohon-seperti-lintasan (path-like-tree), graf kembang api (fire cracker), graf lobster, dan graf rantai (chain graph). Di samping itu kami juga menyajikan metode konstruksi graf total sisi-ajaib (super) baru dari graf yang sudah diketahui total sisi-ajaib (super). Berdasarkan metode ini dihasilkan beberapa kelas graf total sisi-ajaib (super) baru. Beberapa di antaranya memberi dukungan atas kebenaran konjektur bahwa setiap graf pohon mempunyai pelabelan total sisi-ajaib (super). Sedangkan untuk masalah kedua, kami melakukan studi nilai defisiensi graf khususnya pada graf rantai, kipas, kipas ganda, roda, bipartit tak terhubung dan multipartit.