BILANGAN RAINBOW CONNECTION UNTUK BEBERAPA GRAF THORN

Abstract

Abstrak. Misalkan G = (V (G);E(G)) adalah suatu graf terhubung tak trivial. Denisi
pewarnaan c : E(G) ! f1; 2; ; kg; k 2 N, dimana dua sisi yang bertetangga boleh
berwarna sama. Suatu lintasan u 􀀀 v path P di G dinamakan rainbow path jika tidak
terdapat dua sisi di P yang berwarna sama. Graf G disebut rainbow connected jika
setiap dua titik yang berbeda di G dihubungkan oleh rainbow path. Pewarnaaan sisi
yang menyebabkan G bersifat rainbow connected dikatakan rainbow coloring. Bilan-
gan Rainbow connection dari graf terhubung G, ditulis rc(G), didenisikan sebagai
banyaknya warna minimal yang diperlukan untuk membuat graf G bersifat rainbow con-
nected. 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 pewar-
naan c : E(G) ! f1; 2; ; kg sedemikian sehingga G adalah strongly rainbow connected
dikatakan bilangan strong rainbow connection, src(G), di G. Jadi, rc(G) src(G) un-
tuk setiap graf terhubung di G. Pada paper ini akan diulas kembali tentang Bilangan
Rainbow Connection untuk Beberapa Graf Thorn.