Perpustakaan Digital ITB

Pelabelan graf merupakan salah satu topik penting dalam teori graf dengan beragam aplikasi di berbagai bidang seperti teori pengkodean, kristalografi sinar-x, radar, astronomi, desain sirkuit, jaringan komunikasi, dan manajemen basis data. Disertasi ini membahas dua jenis pelabelan graf yakni pelabelan total tak teratur titik dan pelabelan tak teratur-D, dengan D menyatakan himpunan jarak pada suatu graf. Misalkan G adalah graf dan k adalah bilangan bulat positif. Pelabelan-k total tak teratur titik dari graf G adalah suatu pemetaan ' : V (G) [ E(G) ! {1, 2, . . . ,k} sedemikian sehingga semua titik di G memiliki bobot yang berbeda. Bobot dari suatu titik x 2 V (G) didefinisikan sebagai jumlah label x dan label semua sisi yang melekat pada x di G. Nilai total ketakteraturan titik dari G, dinotasikan dengan tvs(G), adalah nilai k terkecil sedemikian sehingga G memiliki pelabelan-k total tak teratur titik. Penentuan nilai total ketakteraturan titik untuk sebarang graf merupakan permasalahan yang kompleks. Nurdin, Baskoro, Salman, dan Gaos (2010a) mengemukakan dua konjektur terkait nilai total ketakteraturan titik pada graf pohon dan graf umum. Konjektur pertama menyatakan bahwa untuk graf pohon T, nilai tvs(T) diberikan oleh tvs(T) = maks{t1, t2, t3}, dimana ti = d(1 + Pi j=1 nj)/(i + 1)e dan nj merupakan banyak titik berderajat j. Sementara itu, konjektur kedua menyatakan bahwa untuk graf umum G dengan derajat minimum "(G) dan derajat maksimum Namun, belum ada studi yang membahas keluarga tak berhingga dari graf pohon maupun graf umum yang tidak memenuhi kedua konjektur tersebut. Oleh karena itu, dalam disertasi ini dikaji konstruksi keluarga tak berhingga dari graf pohon dan graf umum, yang masing-masing memiliki nilai total ketakteraturan titik lebih besar satu dibandingkan dengan nilai pada konjektur pertama dan kedua. Keluarga pohon yang diperoleh membuktikan bahwa konjektur pertama tidak berlaku. Selain itu, keluarga graf umum yang dihasilkan menunjukkan adanya contoh penyangkal lain terhadap konjektur kedua, selain graf K3,4 dan K4,6. Meskipun telah banyak ditemukan kelas-kelas graf pohon yang sesuai dengan konjektur pertama, penentuan nilai total ketakteraturan titik untuk graf pohon secara umum masih menjadi masalah terbuka. Oleh sebab itu, mengidentifikasi kelas-kelas lain dari graf pohon yang memenuhi konjektur pertama merupakan kajian yang menarik. Dalam disertasi ini, dikaji beberapa kelas graf pohon yang memiliki nilai total ketakteraturan titik sesuai dengan konjektur pertama. Selanjutnya, pada disertasi ini diperkenalkan konsep pelabelan tak teratur-D sebagai generalisasi dari berbagai pelabelan tak teratur berbasis jarak yang telah dikembangkan sebelumnya yaitu pelabelan tak teratur jarak non-inklusif dan inklusif serta pelabelan tak teratur jarak-d non-inklusif dan inklusif. Misalkan G adalah graf, D adalah himpunan jarak, dan k adalah bilangan asli. Pelabelan-k tak teratur-D dari graf G adalah suatu pemetaan ' : V (G)!{1, 2, . . . ,k} sedemikian sehingga semua titik di G memiliki bobot yang berbeda, dimana bobot dari suatu titik x 2 V (G) didefinisikan sebagai jumlah label semua titik yang jaraknya dari x termuat dalam D. Nilai k terkecil sedemikian sehingga G memiliki pelabelan-k tak teratur-D disebut nilai ketakteraturan-D dari G dan dinotasikan dengan sD(G). Dalam disertasi ini, disajikan beberapa sifat terkait nilai ketakteraturan-D dari graf sebarang. Selain itu, nilai ketakteraturan-D untuk beberapa kelas graf dengan diameter kecil atau derajat maksimum kecil juga dibahas.