BILANGAN STRONG RAINBOW CONNECTION UNTUK GRAF GARIS, GRAF MIDDLE DAN GRAF TOTAL

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. Bilangan
rainbow connection 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 bilangan strong rainbow connection, src(G), di G. Jadi, rc(G) src(G) untuk
setiap graf terhubung di G. Pada paper ini akan dikaji kembali tentang bilangan strong
rainbow connection untuk graf Garis, graf Middle dan graf Total dari Graf Matahari,
seperti yang telah dibahas dalam [1].