| dc.description.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 | en_US |
