RAINBOW CONNECTION PADA GRAF DENGAN KONEKTIFITAS 1

Voenid Dasti

Jurnal Matematika UNAND
Vol 2, No 2 (2013)

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 banyaknyawarna yang dibutuhkan untuk mewarnai G sehingga G bersifat rainbow connected. Dalamskripsi ini akan dibahas kembali dugaan Caro dkk [3] bahwa rc(G) < 3n4 untuk suatugraf terhubung tak trivial G dengan banyak titik n, derajat minimum (G) 3, dankonektitas (G) = 1.