Perpustakaan Digital ITB

Konsep nilai total ketakteraturan titik pada graf pertama kali diperkenalkan oleh Ba?ca dkk. (2007). Konsep ini merupakan pengembangan dari konsep nilai ketakteraturan yang terlebih dahulu telah dicetuskan oleh Chartrand dkk. (1988). Konsep pelabelan ini memiliki beberapa aplikasi di antaranya dalam representasi senyawa kimia, masalah pengenalan pola, jaringan komputer, struktur data, dan lainnya. Misalkan G(V;E) adalah suatu graf dengan himpunan titik V (G) dan himpunan sisi E(G), fungsi : V (G) [ E(G) ! f1; 2; : : : ; kg disebut pelabelan-k total tak teratur titik pada G jika untuk setiap dua titik yang berbeda di V (G) mempunyai bobot yang berbeda. Bobot titik x di V terhadap fungsi , dinotasikan dengan w(x), adalah w(x) = (x) + P xy2E(G) (xy). Nilai total ketakteraturan titik (total vertex irregularity strength) dari G, dinotasikan dengan tvs(G), didefinisikan sebagai bilangan bulat positif terkecil k sedemikian sehingga G mempunyai suatu pelabelan-k total tak teratur titik. Beberapa kelas graf pohon telah diketahui nilai total ketakteraturan titiknya, di antaranya adalah graf bintang, graf bintang ganda, graf ulat, graf kembang api, graf pohon pisang, dan lainnya. Untuk graf pohon secara umum, Nurdin dkk. (2010a) berhasil menentukan batas bawah nilai total ketakteraturan titiknya sebagai berikut. Misalkan T adalah graf pohon dengan derajat maksimum dan ni adalah banyaknya titik yang berderajat i di T, maka tvs(T) maksft1; t2; t3; : : : ; tg; dengan ti = d(1 + Pi j=1 nj)=(i + 1)e; untuk i 2 [1; ]. Namun demikian, Nurdin dkk. (2010a) menduga bahwa batas atas nilai total ketakteraturan titik graf pohon sama dengan batas bawahnya, sehingga mereka mengajukan sebuah konjektur tentang nilai total ketakteraturan titik graf pohon sebagai berikut. tvs(T) = maks t1; t2; t3 ; dengan ti = d(1 + Xi j=1 nj)=(i + 1)e; untuk i 2 [1; 3]: Konjektur ini menyatakan bahwa nilai total ketakteraturan titik dari sebarang graf pohon dengan derajat maksimum hanya bergantung pada banyaknya titik yang berderajat 1; 2 atau 3. Namun, konjektur ini sulit untuk dibuktikan karena jika diberikan n1; n2; n3 bilangan bulat tak negatif, maka pohon dengan jumlah titik n1; n2; n3 tidak tunggal. Dalam makalah yang sama, diberikan nilai total ketakteraturan titik pohon dengan derajat maksimum 3, pohon yang tidak memiliki titik berderajat 2, lintasan, dan suatu keluarga pohon dengan derajat maksimum 3 yang memuat titik berderajat 2. Semua hasil yang diperoleh ini mendukung kebenaran konjektur (Nurdin dkk., 2010a). Pada disertasi ini, kajian tentang nilai total ketakteraturan titik pada pohon dilanjutkan. Kajian awal adalah menentukan nilai total ketakteraturan titik pohon dengan derajat maksimum 4 atau 5. Hasil yang diperoleh menunjukkan bahwa nilai total ketakteraturan titik pohon dengan derajat maksimum 4 atau 5 hanya bergantung pada banyaknya titik berderajat 1; 2 atau 3. Adapun banyaknya titik yang berderajat 4 atau 5 tidak memberikan kontribusi terhadap nilai total ketakteraturan titik pohon dengan derajat maksimum 4 atau 5. Hasil ini membenarkan konjektur Nurdin dkk. (2010a) tentang nilai total ketakteraturan titik graf pohon. Selanjutnya, kajian ditambah dengan membahas tentang nilai total ketakteraturan titik pohon dengan derajat maksimum 6 dan memuat titik berderajat 2. Pada bagian ini dikarakterisasi pohon dengan derajat maksimum 6 sehingga memiliki nilai total ketakteraturan titik yakni t1; t2 atau t3. Selanjutnya, nilai total ketakteraturan titik pohon tersubdivisi menjadi pembahasan akhir pada disertasi ini. Secara umum, hasil yang diperoleh menunjukkan bahwa nilai total ketakteraturan titik pohon yang tersubdivisi hanya bergantung pada banyaknya titik berderajat 1 dan 2, sehingga t2 = maksft1; t2; t3g: Pada kajian terpisah, diperoleh nilai eksak dari total ketakteraturan titik beberapa kelas graf pohon yang tersubdivisi di sisi punggungnya. Adapun kelas-kelas graf pohon yang dikaji adalah graf ulat, graf kembang api, graf amalgamasi bintang dan graf bintang ganda. Hasil yang diperoleh menunjukkan bahwa nilai total ketakteraturan titik pohon yang tersubdivisi hanya bergantung pada banyaknya titik berderajat 1 dan 2 atau dapat juga ditulis dengan t2 = maksft1; t2; t3g: Sehingga hasil yang diperoleh membenarkan konjektur Nurdin dkk. (2010a)