RAINBOW CONNECTION PADA GRAF DENGAN KONEKTIFITAS 1

Abstract

Misal terdapat graf terhubung sederhana G. Jika diberikan pewarnaan ter-
hadap sisi-sisi G sehingga sebarang dua titik di G dihubungkan oleh suatu lintasan den-
gan semua sisi berwarna berbeda, maka G dikatakan rainbow connected. Rainbow con-
nection number dari graf G, dinotasikan dengan rc(G), adalah minimum dari banyaknya
warna yang dibutuhkan untuk mewarnai G sehingga G bersifat rainbow connected. Dalam
skripsi ini akan dibahas kembali dugaan Caro dkk [3] bahwa rc(G) < 3n
4 untuk suatu
graf terhubung tak trivial G dengan banyak titik n, derajat minimum (G) 3, dan
konektitas (G) = 1.