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

Abstract

Abstrak. Misalkan G = (V (G); E(G)) adalah suatu graf terhubung tak trivial. Suatu pewarnaan
terhadap sisi-sisi di G adalah suatu pemetaan c : E(G) ! f1; 2; ; kg; k 2 N.
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. Bilangan rainbow connection dari graf
terhubung G, ditulis rc(G), didenisikan sebagai banyaknya warna minimal yang diperlukan
untuk membuat graf G bersifat rainbow connected. Suatu Graf Kubik C
merupakan graf kubik terhubung yang terbentuk dari tiga lingkaran dengan banyak titik
pada lingkaran pertama sama dengan lingkaran ketiga yaitu sebanyak n dan banyak titik
pada lingkaran kedua sebanyak 2n dengan himpunan sisi E
merupakan himpunan sisi
yang menghubungkan lingkaran ke-i dengan lingkaran ke- i + 1. Pada paper ini ditunjukkan
bahwa rc(C
5;10;5
) = 7 dan rc(C
6;12;6
) = 8.
Kata Kunci: Graf kubik, graf lingkaran, bilangan rainbow connection
i
n;2n;n