BILANGAN KETERHUBUNGAN PELANGI PADA GRAF GERIGI

Abstract

Pewarnaan pelangi pada graf G adalah suatu pelabelan sisi dengan sifat bahwa setiap pasang simpul dapat dihubungkan oleh lintasan pelangi (lintasan yang warna/label sisinya berbeda semua). Bilangan keterhubungan pelangi rc(G) adalah banyaknya warna paling sedikit pada pewarnaan pelangi di graf G. Graf gerigi (gear) G_n diperoleh dari graf roda (wheel) W_n dengan menyisipkan satu simpul pada setiap sisi lingkaran luar. Penelitian sebelumnya menyelidiki rc(G_n) untuk 2<=n<=8, sedangkan kasus n>=9 belum tertangani. Penelitian ini menutup celah tersebut dengan menunjukkan rc(G_n)=min{4, n} untuk n>=2.