Perpustakaan Digital ITB

Konsep bilangan terhubung pelangi pada graf diperkenalkan pertama kali oleh Chartrand dkk. yang kemudian digeneralisasi menjadi bilangan terhubung-k pelangi untuk graf G yang berhingga dan terhubung-?. Bilangan tersebut dinotasikan dengan rck(G) dan didefinisikan sebagai bilangan bulat positif terkecil j sehingga terdapat pewarnaan-sisi-j yang memenuhi untuk setiap dua titik berbeda u dan v di V (G), terdapat k lintasan u v pelangi yang saling lepas secara internal. Dengan mewarnai setiap sisi di G dengan warna yang berbeda, setiap dua titik di G dapat dihubungkan oleh k lintasan pelangi yang saling lepas secara internal sehingga rck(G) terdefinisi untuk setiap bilangan bulat k dengan 1 ? k ? ?. Penentuan bilangan terhubung-k pelangi untuk sebarang graf tidaklah mudah, bahkan untuk k = 1. Telah dibuktikan bahwa permasalahan tersebut masuk ke dalam permasalahan NP-complete. Oleh karena itu, sebagian peneliti mencoba untuk menentukan bilangan terhubung-k pelangi untuk beberapa kelas graf tertentu. Permasalahan yang dikaji dalam penelitian disertasi ini difokuskan pada penentuan bilangan terhubung-2 pelangi beberapa kelas graf terhubung-2 dan hasil subdi- visinya serta bilangan terhubung-2 pelangi beberapa graf hasil operasi tertentu yang meliputi amalgamasi lintasan, hasil kali sisir sisi, hasil kali Cartesius, dan hasil kali kuat.