Perpustakaan Digital ITB

Graf yang dibahas dalam tesis ini adalah graf sederhana dan berhingga. Misalkan graf G = (V (G),E(G), didefinisikan suatu pewarnaan titik pada G, c : V (G) 7→ {1,2,...,k}untuk suatu bilangan bulat positif k. Suatu lintasan dari graf G disebut lintasan titik pelangi jika titik-titik dalamnya memiliki warna yang berbeda. Graf G dengan pewarnaan titik disebut terhubung titik pelangi jika untuk sebarang dua titik dihubungkan oleh paling sedikit satu lintasan titik pelangi. Bilangan terhubung titik pelangi dari suatu graf G, dinotasikan dengan rvc(G), adalah banyak minimum warna yang dibutuhkan untuk membuat graf G terhubung titik pelangi. Misalkan orde dari G dinotasikan dengan n, Krivelevich dan Yuster telah menunjukkan bahwa diam(G)−1 ≤ rvc(G) ≤ n−2. Jika G memuat q titik potong, maka rvc(G) ≥ q. Pada tesis ini didefinisikan dan ditentukan bilangan terhubung titik pelangi untuk tiga kelas graf baru yaitu graf jari, graf gunung, dan graf perahu.