ANALISIS RAINBOW CONNECTION NUMBER PADA GRAF KHUSUS DAN HASIL OPERASINYA

Abstract

Misalkan G adalah graf terhubung nontrivial dengan edge ¡ coloring c : E(G) ! f1; 2; 3; :::; kg dengan k 2 N, dan mungkin terdapat pewarnaan sisi yang sama pada dua sisi yang bertetangga. Suatu lintasan u ¡ v di G merupakan rainbow path jika tidak ada dua sisi di lintasan tersebut diwarnai sama. Graf G disebut rainbow connected dengan pewarnaan c jika G memuat suatu rainbow u-v path untuk setiap dua titik u; v 2 G. Dalam hal ini pewarnaan c dikatakan rainbow c-coloring di G. Kemudian akan dide¯nisikan rainbow connection number dari graf G dinotasikan dengan rc(G) adalah nilai terkecil yang dibutuhkan untuk mewarnai graf G menjadi rainbow connected. Misalkan c suatu rainbow coloring pada suatu graf terhubung G, Untuk sebarang dua titik u; v 2 G, rainbow u-v geodesic di G adalah suatu rainbow path dengan panjang d(u; v), dimana d(u; v) adalah jarak antara u dan v. Graf G dikatakan strongly rainbow connected jika G memuat satu rainbow u-v geodesic untuk setiap dua titik u dan v pada G. Pada kasus ini c dikatakan strong rainbow c-coloring dari G. Kemudian akan dide¯niskan strong rainbow connection number dari graf G dinotasikan dengan src(G) adalah nilai terkecil yang dibutuhkan untuk mewarnai graf G menjadi strong rainbow connected. Berdasarkan penelitian pada graf khusus dan hasil operasinya meliputi graf prisma, antiprisma, graf join, cartesian product, crown product, tensor product, graf shackle, dan graf amalgamasi telah didapatkan 14 teorema baru terkait rc(G) dan src(G) dan juga beberapa analisis yang menghasilkan 3 conjecture baru, diantaranya adalah sebagai berikut. 1. Teorema 4.2.1 Untuk setiap bilangan bulat m ¸ 2 dan n ¸ 2, nilai rainbow connection number dari graf G = (mPn + K1) adalah rc(mPn + K1) = 3 viii 2. Teorema 4.2.2 Untuk setiap bilangan bulat m ¸ 2 dan n ¸ 2, nilai strong rainbow connection number dari graf G = (mPn + K1) adalah src(mPn + K1) = (d n 3 e)m 3. Teorema 4.2.3 Untuk setiap bilangan bulat n ¸ 3 dan m ¸ 2, nilai rainbow connection number dan strong rainbow connection number dari graf G = Sn¤Pm adalah n + m ¡ 1 4. Teorema 4.2.4 Untuk setiap bilangan bulat n ¸ 3 dan m ¸ 2, nilai rainbow connection number dari graf G = Wn¤Pm adalah rc(Wn¤Pm) = 8>>< >>: m; untuk n = 3 m + 1; untuk 4 · n · 6 m + 2; untuk n ¸ 7: 5. Teorema 4.2.5 Untuk setiap bilangan bulat n ¸ 3 dan m ¸ 2, nilai strong rainbow connection number dari graf G = Wn¤Pm adalah src(Wn¤Pm) = 8>>< >>: rc(Wn¤Pm); untuk n = 3 rc(Wn¤Pm); untuk 4 · n · 6 dn 3 e + m ¡ 1; untuk n ¸ 7: 6. Teorema 4.2.6 Untuk setiap bilangan bulat n ¸ 2 dan m ¸ 3, nilai rainbow connection number dari graf G = Pn ¯ Cm adalah rc(Pn ¯ Cm) = ( 2n ¡ 1; untukm = 3 3n ¡ 1; untukm ¸ 4: ix x 7. Teorema 4.2.7 Untuk setiap bilangan bulat n ¸ 2 dan m ¸ 3, nilai strong rainbow connection number dari graf G = Pn ¯ Cm adalah src(Pn ¯ Cm) = 8>>< >>: rc(Pn ¯ Cm); untukm = 3 rc(Pn ¯ Cm); untuk 4 · m · 6 n(dm 3 e) + (n ¡ 1); untukm ¸ 7 8. Teorema 4.2.8 Untuk setiap bilangan bulat n ¸ 2, nilai rainbow connection number dan strong rainbow connection number dari graf G = shack[(P2 ­ W3); n] adalah 3n. 9. Teorema 4.2.9 Untuk setiap bilangan bulat n ¸ 2, nilai rainbow connection number dan strong rainbow connection number dari graf G = shack[(P3 ­ C3); n] adalah 4n. 10. Teorema 4.2.10 Untuk setiap bilangan bulat n ¸ 2, nilai rainbow connec- tion number dari graf G = Amal[(S4 + K1); v = 1; n] adalah 3. 11. Teorema 4.2.11 Untuk setiap bilangan bulat n ¸ 2, nilai strong rainbow connection number dari graf G = Amal[(S4 + K1); v = 1; n] adalah 2n. 12. Teorema 4.2.12 Untuk setiap bilangan bulat n ¸ 2, nilai rainbow connec- tion number dan strong rainbow connection number dari graf G = Amal[(S4 ¤P2); v = 1; n] adalah 5n. 13. Teorema 4.2.13 Untuk setiap bilangan bulat n ¸ 3 dan m ¸ 1, rainbow connection number dan strong rainbow connection number untuk graf prisma Pr(n;m) adalah rc(Pr(n;m)) = src(Pr(n;m)) = ( m; untuk n = 3 dn 2 e + (m ¡ 1); untuk n ¸ 4 14. Teorema 4.2.14 Untuk setiap bilangan bulat n ¸ 3 dan m ¸ 1, rainbow connection number dan strong rainbow connection number untuk graf an- tiprisma APn adalah rc(APn) = src(APn) = ( 2; untuk n = 3 dn 2 e; untuk n ¸ 4 15. Dugaan 4.3.1 Misalkan G1 dan G2 adalah graf terhubung nontrivial, maka nilai rc(G1 + G2) = 2 dengan G1;G2 bukanlah graf lengkap Kn dan graf disjoin union. 16. Dugaan 4.3.2 Misalkan G adalah graf terhubung nontrivial maka nilai rc(Pn ¯ G) = n[rc(G + v)] + (n ¡ 1). 17. Dugaan 4.3.3 Misalkan G adalah graf terhubung nontrivial maka nilai rc(shack[G; n]) = n[rc(G)]. xi