Perpustakaan Digital ITB

Misalkan k adalah suatu bilangan bulat positif dan G = (V (G);E(G)) adalah graf berhingga dan terhubung. Pewarnaan-k titik pelangi pada G adalah suatu pemetaan c : V (G) ????! f1; 2; :::; kg sehingga untuk setiap dua titik u dan v di G terdapat suatu lintasan titik pelangi yang menghubungkan keduanya. Suatu lintasan P pada G dikatakan lintasan titik pelangi, jika titik-titik dalamnya berwarna berbeda. Bilangan terhubung titik pelangi graf G, dinotasikan dengan rvc(G), adalah bilangan bulat positif terkecil k sehingga terdapat pewarnaan-k titik pelangi pada G. Untuk i 2 f1; 2; :::; kg, misalkan Ri adalah himpunan titik-titik yang diberi warna i dan = fR1;R2; :::;Rkg merupakan partisi terurut dari V (G). Kode pelangi titik v 2 V (G) terhadap adalah tupel-k terurut rc(v) = (d(v;R1); d(v;R2); :::; d(v;Rk)) dengan d(v;Ri) = minfd(v; y)jy 2 Rig untuk i 2 f1; 2; :::; kg. Jika setiap titik di G memiliki kode pelangi yang berbeda, maka pewarnaan c disebut pewarnaan- k pelangi lokasi pada G. Bilangan terhubung pelangi lokasi graf G, dinotasikan dengan rvcl(G), didefinisikan sebagai bilangan bulat positif terkecil k sehingga terdapat suatu pewarnaan-k pelangi lokasi pada G. Permasalahan yang dikaji dalam penelitian disertasi ini difokuskan pada penentuan batas atas dan batas bawah yang ketat untuk bilangan terhubung pelangi lokasi sebarang graf berhingga dan terhubung, serta penentuan bilangan terhubung pelangi lokasi untuk beberapa kelas graf tertentu, yakni beberapa kelas graf bipartit dan beberapa kelas graf transitif titik. Selain itu, dikaji bilangan terhubung pelangi lokasi dari beberapa kelas graf berhingga dan terhubung hasil operasi graf, meliputi graf amalgamasi, graf barbel yang diperumum, dan graf korona sisi.