Perpustakaan Digital ITB

Suatu graf G = (V (G), E(G)) yang dikenakan pewarnaan sisi disebut graf terhubung pelangi jika untuk setiap dua titik di G dihubungkan oleh lintasan yang setiap sisinya mempunyai warna-warna yang berbeda. Lintasan tersebut kemudian disebut dengan lintasan pelangi. Bilangan terhubung pelangi graf G, dinotasikan dengan rc(G), merupakan bilangan bulat positif terkecil yang dibutuhkan dari semua kemungkinan pewarnaan sisi sehingga G terhubung pelangi. Graf G dengan suatu pewarnaan titik disebut graf terhubung titik pelangi apabila untuk setiap dua titik di G dihubungkan oleh lintasan yang setiap titik internal di lintasan tersebut memiliki warna-warna yang tidak sama. Lintasan tersebut disebut dengan lintasan titik pelangi. Bilangan terhubung titik pelangi graf G, dinotasikan dengan rvc(G), merupakan bilangan bulat positif terkecil yang dibutuhkan dari semua kemungkinan pewarnaan titik sehingga G terhubung titik pelangi. Graf splitting dari graf G, dinotasikan dengan Sl(G), adalah graf yang diperoleh dengan menambahkan |V (G)| titik baru sebanyak order G dengan cara untuk setiap titik u di G dibuat sebuah titik baru u0 sedemikian hingga titik u0 hanya bertetangga dengan semua titik yang bertetangga dengan titik u di G. Pada tesis ini, dikaji mengenai batas atas dan bawah bilangan terhubung pelangi dan bilangan terhubung titik pelangi graf splitting. Dalam pengkajian bilangan terhubung pelangi, diberikan nilai bilangan terhubung pelangi untuk graf splitting dari beberapa kelas graf, yaitu graf splitting dari graf lintasan, graf splitting dari graf bintang, graf splitting dari graf kipas, graf splitting dari graf pertemanan dan graf splitting dari graf roda. Untuk bilangan terhubung titik pelangi, diberikan beberapa nilai bilangan terhubung titik pelangi dari graf splitting berdasarkan diameter graf semula, yaitu berdiameter 1 , berdiameter 2, dan berdiameter lebih dari atau sama dengan 3.