Perpustakaan Digital ITB

Pelabelan total tak teratur titik diperkenalkan oleh Baca dkk. (2007). Pelabelan-k total tak teratur titik pada G didefinisikan sebagai suatu pemetaan dari himpunan titik dan himpunan sisi G ke f1;2; : : : ;kg sedemikian sehingga semua titik mempunyai bobot yang berbeda. Bobot titik x 2V adalah jumlah label x dan semua label sisi yang berinsiden dengan x. Nilai total ketakteraturan titik dari G, dilambangkan dengan tvs(G), adalah bilangan bulat positif terkecil k sedemikian sehingga G mempunyai pelabelan-k total tak teratur titik. Beberapa hasil tentang nilai total ketakteraturan titik telah diperoleh untuk beberapa kelas graf. Nurdin, Baskoro, Salman dan Gaos telah menentukan nilai total ketakteraturan titik dari quadtrees dan banana trees. Dalam makalah yang berbeda, mereka juga menghitung nilai total ketakteraturan titik dari lintasan, pohon tanpa titik yang berderajat dua dan tiga. Mereka juga memberikan dugaan bahwa nilai total ketakteraturan titik dari sebarang pohon hanya tergantung pada banyaknya titik yang berderajat 1,2 dan 3 sebagai berikut. tvs(T) = maksft1; t2; t3g dengan ti = d(1+åi j=1 ni)=(i+1)e dan ni adalah banyaknya titik yang berderajat i 2 [1;3]. Pada tesis ini ditentukan nilai total ketakteraturan titik dari graf pohon dengan derajat maksimum empat dan subdivisi beberapa kelas graf pohon yakni subdivisi graf bintang ganda, subdivisi graf ulat, subdivisi graf kembang api, dan subdivisi amalgamasi graf bintang.