Perpustakaan Digital ITB

Graf yang dibahas di dalam tesis ini adalah graf hingga, sederhana, dan tak berarah. Misalkan G = (V (G);E(G)) adalah graf terhubung tak trivial dan m adalah suatu bilangan bulat positif. Didefinisikan c : E(G) ->(1,2,...,m) sebagai suatu pewarnaan-m sisi dari G: Lintasan P di G dikatakan lintasan pelangi, jika tidak terdapat sisi di P yang mempunyai warna yang sama. Misalkan u dan v adalah titik di G, suatu lintasan pelangi dikatakan lintasan pelangi u - v jika lintasan tersebut mempunyai titik ujung u dan v: Bilangan terhubung pelangi dari G dinotasikan dengan rc(G) adalah m terkecil sehingga G mempunyai pewarnaan-m sisi sedemikian sehingga setiap dua titik u,v di G terhubung dengan lintasan pelangi u - v: Jarak antara dua titik u dan v di G dinotasikan dengan d(u; v), adalah panjang dari lintasan terpendek yang menghubungkan kedua titik tersebut. Diameter dari G dino- tasikan oleh diam(G); didefinisikan oleh diam(G) := max d(u; v) untuk setiap u dan v di V (G): Misalkan ukuran dari G dinotasikan dengan l; Chartrand, Johns, McKeon and Zhang memperlihatkan diam(G)< rc(G) < l: Chakraborty, Fischer, Matsilah dan Yuster membuktikan bahwa menghitung bilangan terhubung pelangi dari suatu graf adalah NP- Hard dan jika diberikan suatu pewarnaan sisi graf G, untuk mengecek apakah pewarnaan yang diberikan membuat G terhubung pelangi adalah NP-complete. Dalam tesis ini kami akan memperlihatkan bilangan terhubung pelangi dari graf lingkaran, pertemanan, kipas, dan roda yang dioperasikan dengan operasi korona, Cartesian product, weak product dan strong product dengan lintasan, serta bilangan terhubung pelangi dari graf belenggu yang dikonstruksi dari graf-graf tersebut, selain itu kami juga memperlihatkan batas atas bila- ngan terhubung pelangi dari graf belenggu yang dikonstruksi dari sebarang graf terhubung.