PENENTUAN RAINBOW CONNECTION NUMBER DAN STRONG RAINBOW CONNECTION NUMBER PADA GRAF BERLIAN

Abstract

Misalkan G = (V, E) adalah suatu graf. Suatu pewarnaan c : E(G) → {1, 2, · · · , k}, k ∈ N pada graf G adalah suatu pewarnaan sisi di G sedemikian sehingga setiap sisi bertetangga boleh berwarna sama. Misalkan u, v ∈ V (G) dan P adalah suatu lintasan dari u ke v. Suatu intasan P dikatakan rainbow path jika tidak terdapat dua sisi di P berwarna sama. Graf G disebut rainbow connected dengan pewarnaan c jika untuk setiap u, v ∈ V (G) terdapat rainbow path dari u ke v. Jika terdapat k warna di G maka c adalah rainbow k-coloring. Rainbow connection number dari graf terhubung dinotasikan dengan rc(G), didefinisikan sebagai banyaknya warna minimal yang diperlukan untuk membuat graf G bersifat rainbow connected. Selanjutnya, pewarnaan c dikatakan pewarnaan-k strong rainbow, jika untuk setiap titik u dan v di V terdapat lintasan pelangi dengan panjangnya sama dengan jarak u dan v. Dalam makalah ini akan ditentukan rainbow connection number dan Strong Rainbow Connection Number pada graf Berlian dengan 2n titik. Graf Berlian, dinotasikan dengan Brn, adalah graf yang diperoleh dari graf tangga segitiga dengan 2n − 1 titik, dengan menambahkan satu titik dan beberapa sisi tertentu. Dalam makalah ini akan ditentukan rc(Brn) dan src(Brn) untuk n ≥ 4. Kata Kunci: Rainbow connection number, Strong rainbow connection number, Graf Berlian, Lintasan, Pewarnaan Rainbow