Bilangan Keterhubungan Pelangi Sejati Dari Graf

Abstract

Pewarnaan-sisi pada graf G adalah suatu fungsi W∶E(G)→{1,2,…,k}=[k] di mana [k] adalah himpunan warna. Pewarnaan-sisi-sejati pada graf G merupakan pewarnaan-sisi G di mana setiap dua sisi yang terkait pada titik yang sama berwarna berbeda (Budayasa, 2007). Subgraf H dari G dengan pewarnaan W dikatakan pelangi apabila seluruh sisi H mendapat warna yang berbeda-beda. Graf G dikatakan terhubung pelangi apabila untuk setiap dua titik G, ada lintasan pelangi yang menghubungkan kedua titik tersebut. Bilangan keterhubungan pelangi graf G adalah minimum banyaknya warna yang diperlukan agar G terhubung pelangi, disimbolkan dengan rc(G). Graf nontrivial G dengan pewarnaan-sisi-sejati dikatakan terhubung pelangi sejati apabila untuk setiap dua titik yang berbeda di graf G ada lintasan pelangi yang mengaitkan dua titik tersebut. Bilangan keterhubungan pelangi sejati graf G disimbolkan dengan prc(G). Dalam pembahasan artikel ini, akan ditunjukkan bilangan keterhubungan pelangi sejati pada Graf Pohon (T_n), Graf Sikel (C_n), dan Graf Komplet (K_n). Selain itu, akan ditunjukkan juga batas atas dan batas bawah bilangan keterhubungan pelangi sejati pada graf, besarnya selisih prc(G)-rc(G), dan kelas graf dengan prc(G)=χ'(G).
Kata Kunci: Graf, Pewarnaan-Sisi-Sejati Graf, Bilangan Keterhubungan Pelangi Sejati.