Perpustakaan Digital ITB

Misalkan k adalah suatu bilangan bulat positif dan G = (V,E) adalah graf berhingga dan terhubung. Pewarnaan-k pelangi pada G adalah suatu pemetaan c : E(G) ? {1, 2, ..., k} sehingga untuk setiap dua titik berbeda u dan v di G terdapat lintasan pelangi yang menghubungkan keduanya. Misalkan e = uv dan f = xy adalah elemen sisi di G. Jarak antara dua sisi e dan f, dinotasikan dengan d(e, f), didefinisikan sebagai d(e, f) = ( min{d(u, x), d(u, y), d(v, x), d(v, y)} + 1, jika e ?= f; 0, jika e = f. Untuk 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 yang berbeda, maka pewarnaan c disebut pewarnaan-k sisi pelangi lokasi pada G. Bilangan bulat positif terkecil k sehingga terdapat suatu pewarnaan-k sisi pelangi lokasi pada G disebut bilangan terhubung sisi pelangi lokasi graf G, dinotasikan dengan recl(G). Pada tesis ini, ditentukan batas bawah dan batas atas bilangan terhubung sisi pelangi lokasi pada suatu graf. Selanjutnya ditentukan juga bilangan terhubung sisi pelangi lokasi pada beberapa kelas graf, seperti graf pohon, graf siklus, graf tadpole, graf dumbel, graf ular segitiga, dan graf tangga miring.