Perpustakaan Digital ITB

Graf yang dibahas dalam tesis ini adalah terhubung, hingga, dan sederhana. 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 dua sisi di P yang mempunyai warna yang sama. Misalkan x dan y adalah titik di V (G), suatu lintasan pelangi dikatakan lintasan pelangi x−y jika lintasan tersebut mempunyai titik ujung x dan y. Bilangan terhubung pelangi dari G, dinotasikan dengan rc(G), adalah bilangan bulat positif terkecil m sehingga G mempunyai pewarnaan−m sisi sedemikian sehingga setiap dua titik x dan y di V (G) terdapat lintasan pelangi x−y. Jarak antara dua titik x dan y di V (G), dinotasikan dengan d(x,y), adalah panjang dari lintasan terpendek yang menghubungkan kedua titik x dan y. Diameter dari G, dinotasikan dengan diam(G), didefinisikan sebagai maks{d(x,y)|x,y ∈ V (G)}untuk setiap x dan y di V (G). Misalkan ukuran dari G dinotasikan dengan k, Chartrand, Johns, McKeon, and Zhang memperlihatkan bahwa diam(G) ≤ rc(G) ≤ k. Pada tesis ini didefinisikan empat kelas graf baru yaitu graf bunga (Cm,Kn), graf bunga (Wm,Kn), graf bunga (Cn,Fm), dan graf lemon. Selanjutnya, ditentukan bilangan terhubung pelangi dari empat kelas graf baru tersebut.