BILANGAN KETERHUBUNGAN PELANGI SEJATI DARI GRAF

PROPER RAINBOW CONNECTION NUMBER OF GRAPH

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 (Tn), Graf Sikel (Cn), dan Graf Komplet (Kn). 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.

An edge-coloring of graph G is a function W∶E(G)→{1,2,…,k}=[k] where [k] is set of colors. A proper-edge-coloring in graph G is an edge-coloring G where every two edges that are at the same vertices have a different color (Budayasa, 2007). Subgraph H of G with coloring  W can be said to be rainbow if all edges of H get diferent colors. Graph G is said to be rainbow connected if for every two vertices G, there is a rainbow path connecting the two vertices. The rainbow connection number of graph G is the minimum number of colors needed for G to be rainbow connected, symbolized by rc(G). A nontrivial graph G with proper-edge-coloring is called proper rainbow connected if for every two distinct vertices in graph G there is a rainbow path joining the two vertices. Proper rainbow connection number of graph G is symbolized by prc(G). In the discussion of this article, we will show the proper rainbow connection number in Tree Graph (Tn), Cycle Graph (Cn), and Complete Graph (Kn) Besides that, it will also show the upper bound and lower bound of proper rainbow connection number, the magnitude of the difference from prc(G)-rc(G), and graph classes with prc(G)=χ'(G).

Keywords: Graph, Proper-Edge-Coloring of Graph, Proper Rainbow Connection Number.