RAINBOW CONNECTION NUMBER PADA GRAF (3K6 ∗ W6, v)

Abstract

Misalkan G = (V, E) adalah graf terhubung tak trivial. Definisikan pewarnaan c : E(G) → {1, 2, · · · , k} untuk suatu k ∈ N, dimana sisi yang bertetangga boleh diberi warna yang sama. Misalkan terdapat titik u dan v di G. Suatu lintasan-(u, v) di G dikatakan sebagai lintasan rainbow (rainbow path) jika semua sisi dalam lintasan-(u, v) tersebut memiliki warna yang berbeda. Graf G dikatakan bersifat rainbow connected terhadap pewarnaan c jika G memuat lintasan rainbow untuk setiap dua titik u dan v di G, sementara c dikatakan sebagai pewarnaan rainbow (rainbow coloring) dari G. Jika terdapat k warna yang digunakan dalam pewarnaan tersebut maka c dinamakan pewarnaan-k rainbow (rainbow k-coloring). Bilangan rainbow connection (rainbow connection number ) dari graf terhubung G, dinotasikan dengan rc(G), didefinisikan sebagai banyaknya warna minimum yang diperlukan untuk membuat graf G bersifat rainbow connected. Pada makalah ini akan ditentukan nilai bilangan rainbow connection dari graf yang merupakan hasil amalgamasi tiga graf lengkap, masing-masingnya dengan enam titik, 3K6, dengan graf roda W6, dinotasikan dengan graf (3K6 ∗ W6, v).

Kata Kunci: Graf (3K6 ∗ W6, v), rainbow path, rainbow connection number