Page 108 - Trends in Science and Technology fo Sustainable Living

Trends in Science and Technology 69
for Sustainable Living

Dari penjelasan tersebut, terlihat bahwa graf Petersen
mempunyai bilangan terhubung pelangi yang berbeda dengan
bilangan terhubung pelangi kuat. Namun keadaan ini tidak terjadi
pada graf yang mempunyai bilangan terhubung pelangi kurang
dari 3. Karakteristik ini ditunjukkan dalam Teorema 2 berikut.

Teorema 2. (Chartrand dan Zhang, 2020)
Untuk k ∈ { } dan G graf terhubung non-trivial, rc(G) = k jika dan
1,2
hanya jika src(G) = k.
Selanjutnya, Chartrand dkk. (2008) memberikan contoh
sebarang graf G yang mempunyai rc(G) dan src(G) yang sama.

(a) (b)
Sumber: Chartrand dkk., 2008
Gambar 20. Graf G dengan rc(G) = src(G) = 4

Misalkan pewarnaan-k sisi adalah pemetaan
c′ : ( )E G → { 1,2, ,k } , k ∈  . Perhatikan bahwa graf G pada Gambar
20(a) mempunyai diameter diam(G) = 3, oleh karena itu rc(G)≥3.
Andaikan rc(G) = 3, maka terdapat pewarnaan-3 pelangi pada
graf G. Karena panjang setiap lintasan u - v di G adalah 3, paling
sedikit satu dari tiga lintasan u - v di G adalah sebuah lintasan u
- v pelangi. Misalkan P = ( ,uu 1 ,v 1 ,v ) adalah sebuah lintasan u - v
pelangi. Misalkan c′ (uu )1= , c′ (uv ) = 2 , dan c′ (v v = 3 , seperti
)
1 11 1
yang ditunjukkan pada Gambar 20(b). Jika x dan y adalah dua titik
di G sedemikian hingga d(x, y) = 2, maka G memuat tepat satu
lintasan x - y dengan panjang 2, sementara seluruh lintasan x - y
lainnya mempunyai panjang 4 atau lebih. Hal ini menyatakan secara