Bilangan pelangi terhubung pada graf yang berkaitan dengan sikel

Dalam teori graf konsep pewarnaan terus mengalami perkembangan, salah satunya adalah tentang rainbow connection. Rainbow connection dibagi menjadi 2 jenis, yang pertama adalah pelangi sisi terhubung (rainbow edge-connected), sedangkan yang kedua adalah pelangi titik terhubung (rainbow vertex-connected).

Rainbow edge-connection pada graf G yang terhubung (rc(G)) yaitu bilangan terkecil dari warna yang dibutuhkan untuk membuat graf G menjadi pelangi sisi terhubung, sedangkan Rainbow vertex–connection pada graf G yang terhubung (rvc(G)) merupakan bilangan terkecil dari warna yang dibutuhkan untuk membuat graf G menjadi pelangi titik terhubung. Pada penelitian ini akan dibahas tentang bilangan bilangan rc(G)dan rvc(G) pada sikel, graf roda, graf gear, graf helm, graf helm tertutup, dan graf bunga

Berdasarkan penelitian diperoleh bahwa rumus umum untuk rc pada graf sikel (C_n) adalah rc(C_n)=1 jika n=3 dan rc(C_n)=⌈n/2⌉ untuk n≥4. rc pada graf roda (W_n) adalah rc (W_n) =1 jika n=3, rc (W_n) =2 jika 4≤n≤6 , dan rc (W_n) =3 jika n≥7 pada graf gear G_n adalah rc(G_n) = n untuk n≥3. rc pada graf helm (H_n) adalah rc(H_n )=rc(W_n)+n untuk n≥3. rc pada graf helm tertutup (cH_n) adalah rc (cH_n)=2 jika n=3, rc (cH_n)=3 jika 4≤n≤5 , dan rc (cH_n)=4 jika n≥6. Dan rc pada graf bunga (Fl_n) adalah rc(Fl_n) =1 jika n=3 dan rc(Fl_n)=3 untuk n≥4. Sedangkan rvc pada graf sikel (C_n) adalah rvc(C_n)=0 jika n=3, rvc(C_n)=1 jika n=4&5 , rvc(C_n)=3 jika n=9 , rvc(C_n)= ⌈n/2⌉-1 jika n=6,7,8,10,11,12,13, atau 15, dan rvc(C_n)=⌈n/2⌉ jika n≥16atau n=14 , rvc pada graf roda (W_n) adalah rvc(W_n)=0 jika n=3 , dan rvc(W_n)=1 jika n≥4. rvc pada graf gear (G_n) adalah rvc (G_n) =2 untuk n=3 dan rvc (G_n) =3 jika n≥4. rvc pada graf helm (H_n) adalah rvc(H_n)=2 jika n=3, dan rvc(H_n)=3 jika n≥4. rvc pada graf helm tertutup (cH_n) adalah rvc(cH_n)=1 jika n=3, rvc(cH_n)=2 jika 4≤n≤6, rvc(cH_n)=3 jika 7≤n≤10, dan rvc(cH_n)=4 jika n≥11. Dan rvc pada graf bunga (FI_n) adalah rvc(FI_n)=1 untuk n≥3.

Pada skripsi ini, penulis hanya memfokuskan pada pokok bahasan pada graf yang berkaitan dengan sikel. Maka dari itu dapat dikaji dengan jenis graf yang lain.

ENGLISH:

In the graph teory, concept of colouring immediately work out. It’s one of rainbow connection. Rainbow connection is divided into two parts, the first isi rainbow edge connection and the second is rainbow vertex connection

The rainbow edge-connection of a connected graph G (rc(G)) is the smallest number of colors that are needed in order to make graph G rainbow edge connected, and then the rainbow vertex-connection of a connected graph G (rvc(G)) is the smallest number of colors that are needed in order to make G rainbow vertex-connected. This research was analysis about number of rc(G) and rvc(G) from cycle graph, wheel graph, gear graph, helm graph, closed helm graph, and flower graph.

The result show that conclusion from this research are rc from cycle graph (C_n) are rc(C_n)=1 if n=3 and rc(C_n)=⌈n/2⌉ if n≥4. rc fron wheel graph (W_n) are rc (W_n) =1 if n=3, rc (W_n) =2 if 4≤n≤6, and rc (W_n) =3 if n≥7 from gear graph G_n is rc(G_n)=n if n≥3. rc from helm graph (H_n) is rc(H_n)=rc(W_n)+n if n≥3. rc from closed helm graph (cH_n) are rc (cH_n)=2 if n=3, rc (cH_n)=3 if 4≤n≤5, and rc (cH_n)=4 if n≥6 . And rc from flower graph (Fl_n) are rc(Fl_n) =1 if n=3 and rc(Fl_n)=3 if n≥4. And then rvc from cycle graph (C_n) are rvc(C_n)=0 if n=3, rvc(C_n)=1 if n=4&5, rvc(C_n)=3 if n=9, rvc(C_n)= ⌈n/2⌉-1 if n=6,7,8,10,11,12,13, or 15, and rvc(C_n)=⌈n/2⌉ if n≥16 or n=14, rvc from wheel graph (W_n) are rvc(W_n)=0 if n=3, and rvc(W_n)=1 if n≥4. rvc from gear graph (G_n) are rvc (G_n) =2 if n=3 and rvc (G_n) =3 if n≥4. rvc from helm graph (H_n) are rvc(H_n)=2 if n=3, and rvc(H_n)=3 if n≥4. rvc from closed helm graph (cH_n) are rvc(cH_n)=1 if n=3, rvc(cH_n)=2 if 4≤n≤6, rvc(cH_n)=3 if 7≤n≤10, and rvc(cH_n)=4 if n≥11. And rvc from flower graph (FI_n) isrvc(FI_n)=1 if n≥3.

This thesis just focuses on graph that related to cycle. So from that, it can be analyzed by another graph.