Perpustakaan Digital ITB

MisalkanGdanH merupakan dua graf tak trivial, sederhana, hingga, dan terhubung. Untuk suatu k ? N, didefinisikan suatu pewarnaan c : E(G) ? [1, k] merupakan pewarnaan-k pelangi jika untuk setiap titik u ? V(G) dan v ? V(G) terdapat lintasan u?v sedemikian sehingga sisi-sisi dalamnya memiliki warna yang berbeda. Misalkan a = uv dan b = xy merupakan anggota sisi di G. Jarak antara dua sisi a dan b, dinotasikan dengan d(a, b) yang didefinisikan sebagai d(a, b) = ??????? min{d(u, x), d(u, y), d(v, x), d(v, y)} + 1, jika a , b; 0, jika a = b. Untuk setiap i ? {1, 2, . . . , k}, misalkan Ri adalah himpunan sisi dengan warna i dan ? = {R1,R2, . . . ,Rk} merupakan partisi terurut dari E(G). Kode pelangi dari sisi e ? E(G) terkait ? dinotasikan dengan rc?(e) = (d(e,R1), d(e,R2), . . . , d(e,Rk)) dengan d(e,Ri) = min{d(e, y) : y ? Ri} untuk setiap i ? {1, 2, . . . , k}. Jika setiap sisi di G memiliki kode pelangi berbeda, maka pewarnaan c disebut pewarnaan-k sisi pelangi lokasi pada G. Bilangan bulat positif terkecil k sehingga G memiliki pewarnaan-k sisi pelangi lokasi adalah bilangan terhubung sisi pelangi lokasi dari G, dinotasikan dengan recl(G). Untuk suatu u ? V(H), operasi sisir G dengan H, dinotasikan dengan G ?u H, adalah graf yang diperoleh dengan mengambil satu duplikasi G dan |V(G)| duplikat dari H dan mengidentifikasi duplikat ke-i dari H pada titik u terhadap titik ke-i dari G. Pada penelitian ini, diberikan batas bawah dan batas atas yang ketat untuk bilangan terhubung sisi pelangi lokasi hasil operasi sisir dua graf. Selanjutnya ditentukan bilangan terhubung sisi pelangi lokasi hasil operasi sisir dua graf untuk beberapa kelas graf G dan H, yaitu operasi sisir graf pohon dengan graf pohon, graf payung dengan graf pohon, graf siklus dengan graf pohon, graf pohon dengan graf siklus dan graf siklus dengan graf siklus.