BILANGAN STRONG RAINBOW CONNECTION UNTUK GRAF RODA DAN GRAF KUBIK
Abstract
Abstrak. Misalkan G = (V (G); E(G)) adalah suatu graf terhubung tak trivial. Denisikan
suatu 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. Pewarnaan
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 sedemikian sehingga G adalah strongly rainbow connected dikatakan bilangan strong
rainbow connection, src(G), di G. Pada paper ini akan dikaji tentang bilangan strong
rainbow connection untuk graf Roda dan graf Kubik.
suatu 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. Pewarnaan
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 sedemikian sehingga G adalah strongly rainbow connected dikatakan bilangan strong
rainbow connection, src(G), di G. Pada paper ini akan dikaji tentang bilangan strong
rainbow connection untuk graf Roda dan graf Kubik.
Full Text:
PDFDOI: https://doi.org/10.25077/jmu.5.4.72-79.2016
Refbacks
- There are currently no refbacks.
Copyright (c) 2016 Jurnal Matematika UNAND
Ciptaan disebarluaskan di bawah Lisensi Creative Commons Atribusi-BerbagiSerupa 4.0 Internasional.