RAINBOW CONNECTION PADA BEBERAPA GRAF
Abstrak: 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. Minimum 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 ste, sedangkan rainbow connection
number dari graf bipartit lengkap Ks;t dengan 2 s t dimana s; t 2 N
adalah rc(Ks;t) = minfd spte; 4g.
Penulis: GEMA HISTA MEDIKA
Kode Jurnal: jpmatematikadd130098
