PENENTUAN BILANGAN RAINBOW CONNECTION DARI AMALGAMASI GRAF RODA

Abstract

Abstrak. Suatu pewarnaan terhadap sisi-sisi di graf G terhubung tak trivial didenisikan
sebagai c : E(G) ! f1; 2; ; kg; k 2 N adalah pewarnaan sedemikian sehingga
setiap sisi bertetangga boleh berwarna sama. Terdapat u dan v di V (G) dan P adalah
lintasan dari u ke v. Graf P dikatakan rainbow path jika tidak terdapat dua sisi di P yang
berwarna sama. Graf G disebut rainbow connected jika untuk setiap u; v 2 V (G) terdapat
rainbow path antara u dan v. Dalam hal ini, pewarnaan c dikatakan rainbow coloring
di G. Jika terdapat k warna di G maka c adalah rainbow k-coloring. Nilai minimum k
sehingga terdapat rainbow k-coloring di G disebut dengan bilangan rainbow connection,
ditulis rc(G). Penelitian ini menentukan bilangan rainbow connection dari amalgamasi
graf roda, rc(Amal(W
n
; t; v
i0
)), dimana graf Amal(W
n
; t; v
) adalah graf yang berasal
dari hasil penyatuan titik sebanyak t, yang masing-masingnya diambil dari satu titik
pusat W
n
, dan v
i0
i0
menyatakan titik yang menjadi hasil amalgamasi, seperti yang telah
dibahas dalam [6].
Kata Kunci: Amalgamasi, Graf Roda, Rainbow Path, Rainbow Connected, Bilangan
Rainbow Connection