BATAS ATAS BILANGAN RAINBOW CONNECTION UNTUK GRAF KUBIK C n;2n;2n;2n;n

Abstract

Abstrak. Misalkan G merupakan suatu graf terhubung tak trivial. Didenisikan suatu
pewarnaan c : E(G) ! f1; 2; ; ng; n 2 N, dimana sisi yang bertetangga boleh
berwarna sama. Suatu lintasan u  v path dikatakan sebagai rainbow path pada G jika
tidak terdapat dua sisi pada path yang berwarna sama. Suatu graf G dikatakan rainbowconnected
terhadap pewarnaan sisi, jika G memuat rainbow u-v path untuk setiap dua
titik u dan v pada G. Jika graf G bersifat rainbow connected maka pewarnaan sisinya
dinamakan rainbow coloring pada G. Bilangan rainbow connection (rc) (rainbow connection
number) dari G, dilambangkan dengan rc(G), didenisikan sebagai minimum
banyaknya warna yang diberikan pada G sedemikian sehingga G merupakan rainbow
(rainbow connected). Suatu Graf Kubik C
adalah suatu graf kubik yang
dibentuk dari lima buah lingkaran dengan banyak titik lingkaran pertama sama dengan
banyak titik lingkaran kelima yaitu sebanyak n dan lingkaran ke-dua, ke-tiga, dan keempat
adalah sebanyak 2n dengan himpunan sisi E
n;2n;2n;2n;n
merupakan himpunan sisi yang
menghubungkan lintasan ke-i dengan lingkaran ke-i +1. Pada paper ini akan dibuktikan
bahwa batas atas bilangan Rainbow Connection untuk Graf kubik C
i
adalah
11 dan Graf kubik C
6;12;12;12;6
adalah 14.
Kata Kunci: Graf kubik, graf cycle, bilangan rainbow connection
5;10;10;10;5