RAINBOW CONNECTION NUMBER DAN STRONG RAINBOW CONNECTION NUMBER PADA GRAF TANGGA SEGITIGA YANG DIPERUMUM

Abstract

Abstrak. Misalkan G adalah graf terhubung tak trivial dengan pewarnaan c : E(G) !
f1; 2; ; kg, k 2 N, untuk sisi dari G, dimana sisi yang bertetangga boleh diberi warna
yang sama. Misal terdapat titik u dan v di G, sebuah lintasan P di G adalah rainbow path
jika tidak ada dua sisi dari titik u dan v di P memiliki warna yang sama. Graf G adalah
rainbow connected dengan pewarnaan c jika G memiliki rainbow path untuk setiap dua
titik u; v 2 V (G). Rainbow connection number dari graf terhubung dinotasikan dengan
rc(G), didenisikan sebagai banyaknya warna minimum yang diperlukan untuk membuat
graf G bersifat rainbow connected.
Untuk dua titik u dan v dari G, sebuah rainbow geodesic (u; v) di G adalah rainbow
path (u; v) dengan panjang d(u; v) dimana d(u; v) adalah jarak diantara u dan v (panjang
path (u; v) terpendek di G). Graf G adalah strongly rainbow connected jika G memiliki
sebuah rainbow geodesic (u; v) untuk setiap dua titik u dan v di G. Minimum k yang
terdapat pada pewarnaan c : E(G) ! f1; 2; ; kg dari sisi G sedemikian sehingga
G strongly rainbow connected dinamakan strong rainbow connection number, src(G).
Pada tulisan ini akan dibahas rainbow connection number dan strong rainbow connection
number pada graf tangga segitiga yang diperumum Tr
4
.
Kata Kunci: Rainbow connection number, Strong rainbow connection number, graf
tangga segitiga yang diperumum