BILANGAN RAINBOW CONNECTION UNTUK BEBERAPA GRAF THORN
Abstrak: Misalkan G = (V (G),E(G))
adalah suatu graf terhubung tak trivial. Definisi pewarnaan c : E(G) → {1,2,···
,k},k ∈ 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. Bilangan Rainbow connection dari graf terhubung G, ditulis
rc(G), didefinisikan 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) → {1,2,··· ,k}
sedemikian sehingga G adalah strongly rainbow connected dikatakan bilangan
strong rainbow connection, src(G), di G. Jadi, rc(G) ≤ src(G) untuk setiap graf
terhubung di G. Pada paper ini akan diulas kembali tentang Bilangan Rainbow
Connection untuk Beberapa Graf Thorn.
Penulis: MELVI MUCHLIA
Kode Jurnal: jpmatematikadd160413
