BATAS ATAS RAINBOW CONNECTION NUMBER PADA GRAF BUCKMINSTERFULLERENE

Abstract

Misalkan G adalah suatu graf terhubung tak trivial. 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 lintasan 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. Dalam makalah ini akan ditentukan batas atas Rainbow Connection Number pada Graf Buckminsterfullerene.

Kata Kunci: Graf Buckminsterfullerene, Rainbow connection number