Perpustakaan Digital ITB
Suatu pelabelan titik pada graf dikatakan istimewa jika satu-satunya automorfisma
yang mengawetkan pelabelan tersebut hanyalah identitas. Bilangan istimewa (distinguishing number) dari graf G adalah nilai terkecil m sedemikian hingga G memiliki
pelabelan?m istimewa, dilambangkan dengan D(G). Untuk suatu partisi?k berurutan
? = {S1, S2, ..., Sk} dari V (G), representasi r(v|?) dari titik v terhadap ? adalah
(d(v, S1), ..., d(v, Sk)), di mana d(v, S) = min{d(v, x)|x ? S}. Partisi ? tersebut
merupakan partisi pembeda dari G bila semua vektor r(v|?) berbeda untuk semua v ? G.
Nilai terkecil k di mana terdapat partisi pembeda dengan k kelas partisi dari graf G
dinamakan dimensi partisi G, dilambangkan dengan pd(G). Partisi V (G) menjadi k kelas
partisi dapat dipandang sebagai pelabelan setiap titik di V (G) ke {1, 2, ..., k}.
Pelabelan istimewa yang ditemukan pada tahun 1996 dan partisi pembeda yang ditemukan
pada tahun 2000 merupakan dua aturan pelabelan titik yang menarik minat para peneliti di
bidang teori graf selama lebih dari 2 dekade. Berdasarkan definisinya, pelabelan istimewa
didasarkan atas automorfisma titik, yang mana sifat automorfisma adalah mempertahankan
ketetanggaan dari setiap titik yang dipetakan. Diperhatikan bahwa ketetanggaan titik
berkaitan erat dengan jarak antar titik pada graf yang merupakan parameter dasar dalam
menentukan partisi pembeda suatu graf. Oleh karena itu, cukup masuk akal bila kita
menduga terdapat kaitan erat antara dua aturan pelabelan titik tersebut, sesuatu yang belum
pernah diteliti hingga saat ini.
Baik bilangan istimewa maupun dimensi partisi untuk beberapa kelas graf telah ditemukan.
Di antaranya, graf siklus, graf lintasan, graf lengkap, graf Petersen, graf hypercube, graf
bintang, graf bipartit lengkap, graf roda (batas atas dan bawah) , graf pohon ulat, pohon
firecrackers, subdivisi pohon, dan beberapa struktur pohon lainnya. Namun demikian,
hingga saat ini belum ada penelitian yang mengkaji kaitan antara kedua parameter tersebut.
Bila kaitan tersebut diketahui, maka pengetahuan mengenai dimensi partisi suatu kelas
graf dapat digunakan untuk mencari nilai bilangan istimewa dari kelas graf tersebut, dan
sebaliknya. Penelitian disertasi ini akan memberi fokus perhatian pada kaitan dari kedua
parameter graf tersebut.
Secara lebih spesifik, penelitian disertasi ini berfokus pada kaitan umum dan kaitan khusus
antara bilangan istimewa dan dimensi partisi graf sederhana terhubung. Kami berhasil
menunjukkan bahwa untuk setiap graf G dimensi partisi merupakan batas atas bagi bilangan
istimewa, yaitu D(G) ? pd(G). Kami juga menemukan beberapa kelas graf yang
memenuhi D(G) = pd(G), di antaranya Pn, K1,n, Kn, Kn,n, graf bintang ganda Sm,n, dan Cn. Dengan menggunakan pengetahuan mengenai karakterisasi graf berorde n dan
dimensi partisi n ? 1 atau n ? 2, kami berhasil mendapatkan beberapa kelas graf yang
memenuhi pd(G) ? D(G) = 1 dan pd(G) ? D(G) = 2. Selisih antara dimensi partisi
dan bilangan istimewa ini bisa menjadi sangat jauh, yang dapat dilihat contohnya pada graf
theta umum dan juga graf roda. Sifat dimensi partisi terkait banyaknya titik kembar ternyata
juga dimiliki oleh bilangan istimewa.
Selain relasi umum antara dua pelabelan itu, dalam disertasi ini kami juga membahas
pelabelan istimewa untuk kelas graf terhubung yang tidak memuat cycle, yaitu graf pohon.
Bilangan istimewa maupun dimensi partisi untuk sebarang pohon hingga saat ini belum
diketahui. Dalam penelitian ini kami mengkaji pohon berjari-jari 1 dan 2 dengan memperkenalkan notasi tuple. Dengan menggunakan notasi tersebut, dapat ditentukan bilangan
istimewa setiap pohon dengan radius tidak melebihi 2. Kami menunjukkan bahwa untuk
setiap bilangan bulat positif d, dapat dilakukan karakterisasi semua graf pohon T dengan
rad(T) ? 2 dan bilangan istimewa d.