RAINBOW CONNECTION PADA BEBERAPA GRAF

Abstract

Misalkan G adalah graf terhubung tak-trivial. Denisikan pewarnaan c :
E(G) ! f1; 2; :::; kg, k 2 N, dimana dua sisi yang bertetangga boleh memiliki warna
yang sama. Suatu u 􀀀 v path P di G dikatakan rainbow path jika tidak ada dua sisi di
P yang memiliki warna sama. Graf G dikatakan rainbow connected jika setiap dua titik
yang berbeda di G dihubungkan oleh rainbow path. Pewarnaan sisi yang menyebabkan G
bersifat rainbow connected dikatakan rainbow coloring. Rainbow connection number dari
graf terhubung G, ditulis rc(G), didenisikan sebagai banyaknya warna minimal yang
diperlukan untuk membuat graf G bersifat rainbow connected. Misalkan c adalah rainbow
coloring dari graf terhubung G. Untuk dua titik u dan v di G, rainbow u-v geodesic pada
G adalah rainbow u-v path yang panjangnya d(u; v), dimana d(u; v) adalah jarak antara
u dan v (panjang u-v path terpendek di G). Graf G dikatakan strongly rainbow-connected
jika G memiliki suatu rainbow u-v geodesic untuk setiap dua titik u dan v di G. Mini-
mum k yang terdapat pada pewarnaan c : E(G) ! f1; 2; :::; kg sedemikian sehingga G
adalah strongly rainbow-connected dikatakan strong rainbow connection number, src(G);
di G. Jadi, rc(G) src(G) untuk setiap graf terhubung di G. Pada paper ini akan di-
ulas kembali tentang strong rainbow connection number dari graf bipartit lengkap Ks;t
dengan 1 s t dimana s; t 2 N adalah src(Ks;t) = d s
p
te, sedangkan rainbow connec-
tion number dari graf bipartit lengkap Ks;t dengan 2 s t dimana s; t 2 N adalah
rc(Ks;t) = minfd s
p
te; 4g.