Jurnal Matematika UNAND Vol. 5 No. 3 Hal. 65 – 76 ISSN : 2303–2910 c
Jurusan Matematika FMIPA UNAND
BILANGAN RAINBOW CONNECTION UNTUK BEBERAPA GRAF THORN MELVI MUCHLIAN Program Studi Magister Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Andalas, Kampus UNAND Limau Manis Padang, Indonesia, email :
[email protected]
Abstrak. Misalkan G = (V (G), E(G)) adalah suatu graf terhubung tak trivial. Definisi pewarnaan c : E(G) → {1, 2, · · · , k}, k ∈ N , dimana dua sisi yang bertetangga boleh berwarna sama. Suatu lintasan u − v path P di G dinamakan rainbow path jika tidak terdapat dua sisi di P yang berwarna sama. Graf G disebut rainbow connected jika setiap dua titik yang berbeda di G dihubungkan oleh rainbow path. Pewarnaaan sisi yang menyebabkan G bersifat rainbow connected dikatakan rainbow coloring. Bilangan Rainbow connection dari graf terhubung G, ditulis rc(G), didefinisikan sebagai banyaknya warna minimal yang diperlukan untuk membuat graf G bersifat rainbow connected. Misalkan c adalah rainbow coloring dari graf terhubung G. Untuk dua titik u dan v di G, rainbow u − v geodesic pada G adalah rainbow u − v path yang panjangnya d(u, v) dimana d(u, v) adalah jarak antara u dan v (panjang u − v path terpendek di (G). Graf G dikatakan strongly rainbow connected jika G memiliki suatu rainbow u − v geodesic untuk setiap dua titik u dan v di G.Minimum k yang terdapat pada pewarnaan c : E(G) → {1, 2, · · · , k} sedemikian sehingga G adalah strongly rainbow connected dikatakan bilangan strong rainbow connection, src(G), di G. Jadi, rc(G) ≤ src(G) untuk setiap graf terhubung di G. Pada paper ini akan diulas kembali tentang Bilangan Rainbow Connection untuk Beberapa Graf Thorn. Kata Kunci: Bilangan Rainbow Connection, graf Thorn
. 1. Pendahuluan Konsep rainbow connection dari suatu graf pertama kali diperkenalkan oleh Chartrand, Johns, McKeon dan Zhang [3] pada tahun 2008. Misalkan G = (V (G), E(G)) adalah suatu graf terhubung tak trivial. Definisi pewarnaan c : E(G) → {1, 2, · · · , k}, k ∈ N , dimana dua sisi yang bertetangga boleh berwarna sama. Suatu lintasan u − v path P di G dinamakan rainbow path jika tidak terdapat dua sisi di P yang berwarna sama. Graf G disebut rainbow connected jika setiap dua titik yang berbeda di G dihubungkan oleh rainbow path. Pewarnaaan sisi yang menyebabkan G bersifat rainbow connected dikatakan rainbow coloring. Jelas jika G adalah rainbow connected, maka G terhubung. Sebaliknya, setiap graf terhubung memiliki pewarnaan sisi trivial sehingga G bersifat rainbow connected, yaitu setiap sisi diwarnai dengan warna berbeda. Bilangan Rainbow connection dari graf terhubung G, ditulis rc(G), didefinisikan sebagai banyaknya warna minimal yang diperlukan untuk membuat graf G bersifat rain65
66
Melvi Muchlian
bow connected. Suatu rainbow coloring yang menggunakan sebanyak rc(G) warna dikatakan minimum rainbow coloring. Misalkan c adalah rainbow coloring dari graf terhubung G. Untuk dua titik u dan v di G, rainbow u − v geodesic pada G adalah rainbow u − v path yang panjangnya d(u, v) dimana d(u, v) adalah jarak antara u dan v (panjang u − v path terpendek di (G). Graf G dikatakan strongly rainbow connected jika G memiliki suatu rainbow u − v geodesic untuk setiap dua titik u dan v di G. Dalam kasus ini, pewarnaan c dikatakan strong rainbow coloring di G. Minimum k yang terdapat pada pewarnaan c : E(G) → {1, 2, · · · , k} sedemikian sehingga G adalah strongly rainbow connected dikatakan bilangan strong rainbow connection atau strong rainbow connection number, src(G), di G. Suatu strong rainbow coloring di G yang menggunakan src(G) warna dikatakan minimum strong rainbow coloring di G. Jadi, rc(G) ≤ src(G) untuk setiap graf terhubung di G [3]. Selanjutnya, jika G adalah graf terhubung tak trivial dengan ukuran m dan diam(G) = max{d(u, v)|u, v ∈ V (G)}, maka diam(G) ≤ rc(G) ≤ src(G) ≤ m. Pada paper ini akan dikaji tentang Bilangan Rainbow Connection untuk Beberapa Graf Thorn. 2. Bilangan Rainbow Connection Berikut disajikan kembali propositionosisi yang membahas tentang graf G yang mempunyai rc(G) dan src(G) 1, 2 dan m. Proposisi 2.1. [3] Misalkan G adalah suatu graf terhubung tak trivial yang berukuran m. Maka (1) rc(G) = src(G) = 1 jika dan hanya jika G merupakan graf lengkap, (2) rc(G) = 2 jika dan hanya jika src(G) = 2, dan (3) rc(G) = src(G) = m jika dan hanya jika G suatu graf pohon. Proposisi 2.2. [3] Untuk setiap bilangan bulat positif n ≥ 4, rc(Cn ) = src(Cn ) = d n2 e. Definisi 2.3. [7] Misalkan l1 , l2 , · · · , ln adalah bilangan-bilangan bulat positif dan G adalah suatu graf dengan V (G) = {v1 , v2 , · · · , vn }. Thorn dari graf G, dengan parameter l1 , l2 , · · · , ln diperoleh dengan menghubungkan li titik baru berderajat 1 ke titik vi dari graf G(i ∈ 1, · · · , n). Graf thorn dari graf G dinotasikan dengan G∗ atau G∗ (l1 , l2 , · · · , ln ) jika masingmasing parameter ditentukan. Contoh graf thorn diperlihatkan pada Gambar 1. Teorema berikut menyajikan bilangan rainbow connection untuk graf thorn dari graf lengkap. Pada teorema berikut akan ditinjau graf thorn untuk setiap li ≥ n (i ∈ {1, · · · , n}) Teorema 2.4. [7] Untuk n ≥ 1 dan li ≥ n, berlaku rc(Kn∗ ) = src(Kn∗ ) =
n X i=1
li .
Bilangan Rainbow Connection untuk Beberapa Graf Thorn
67
Gambar 1. Graf C4∗ (l1 , l2 , · · · , l4 ).
Bukti. Perhatikan bahwa uij adalah thorn dari titik vi (i ∈ {1, · · · , n}, j ∈ {1, · · · , li }). Perhatikan Gambar 2.
Gambar 2. Graf K4∗
Pn Terlebih dahulu akan ditunjukkan bahwa rc(Kn∗ ) ≤ i=1 li . Karena semua path dari ui1 j1 ke ui2 j2 perlu melalui sisi ui1 j1 vi1 , vi2 ui2 j2 , ini jelas bahwa warna dari sisi vi uij dimana (i ∈ {1, · · · , n}, j ∈ {1, · · · , li }) haruslah berbeda. Dengan kata lain, ini merupakan syarat perlu untuk rainbow connectivity suatu graf. Oleh karena itu, dalam pewarnaan ini warnai semua sisi thorn vi uij dengan c(vi uij ) = j (i) dimana j (i) , i ∈ {1, · · · , n}, j ∈ {1, · · · , li } terlebih dahulu sebagai kode pewarnaan dari sisi graf. Warnai sisi lain dengan cara berikut. c(vi vj ) = (j + 1)(i+1) , untuk i < j < n, i ∈ {1, · · · , n}, j ∈ {1, · · · , li }, c(vi vn ) = 1(i+1) , untuk i ∈ {1, · · · , n}, c(vn v1 ) = 2(2) . Hal ini jelas bahwa lintasan dari ui1 j1 vi1 − vi1 vi2 − vi2 ui2 j2 dengan pewarnaan (i ) − (i2 + 1)(i1 +1) − j2 2 sedangkan ui1 j1 vi1 − vi1 vn − vn unj2 dengan pewar(n) (1) (i ) (n) naan j1 1 − 1(i1 +1) − j2 . j1 − 2(2) − j2 adalah kode pewarnaan dari lintasan unj1 vn − vn v1 − v1 u1j2 . Semua lintasan dari graf memiliki warna yang berbeda. Dengan kata lain, setiap dua titik dari graf Kn∗ merupakan lintasan rainbow conPn Pn nected dengan i=1 li warna. Jadi, dapat dibangun sebuah rainbow i=1 li -coloring (i ) j1 1
68
Melvi Muchlian
dari Kn∗ sehingga dapat membuat graf Kn∗ rainbow connected. Ini berarti bahwa Pn rc(Kn∗ ) ≤ i=1 li . Pn Selanjutnya, akan ditunjukkan bahwa rc(Kn∗ ) ≥ i=1 li . Asumsikan berlawanan P Pn n sehingga rc(Kn∗ ) ≤ i=1 li − 1. Misalkan c1 adalah rainbow i=1 li − 1-coloring dari Kn∗ . Misalkan bahwa ui1 j1 vi1 dan vi2 ui2 j2 adalah dua sisi dengan warna yang sama, maka lintasan ui1 j1 − ui2 j2 di Kn∗ bukanlah rainbow path. Ini menyebabkan Pn ∗ kontradiksi, haruslah rc(Kn∗ ) ≥ i=1 li , selanjutnya diperoleh bahwa rc(Kn ) = Pn i=1 li . Kemudian, akan ditunjukkan bahwa c rainbow coloring adalah strong rainbow coloring. Karena ui1 j1 vi1 − vi1 vi2 − vi2 ui2 j2 adalah lintasan dengan panjang d(ui1 j1 , ui2 j2 ) antara ui1 j1 dan ui2 j2 di Kn∗ , dimana i1 , i2 ∈ {1, · · · , n} dan i1 6= i2 , j1 ∈ {1, · · · , li1 }, j2 ∈ {1, · · · , li2 }, sehingga c rainbow coloring dapat memPn buat Kn∗ strongly rainbow connected. Jadi diperoleh src(Kn∗ ) ≤ i=1 li . P n Selanjutnya, akan ditunjukkan bahwa src(Kn∗ ) ≥ i=1 li . Misalkan tanpa menPn ∗ gurangi keumuman sehingga src(Kn ) = i=1 li − 1. Terdapat paling sedikit dua sisi thorn yang berwarna sama, maka rainbow geodesic dari satu thorn dengan yang Pn lainnya tidak ada, sehingga ini kontradiksi. Oleh karena itu src(Kn∗ ) = i=1 li . P P n n Akibatnya, karena rc(Kn∗ ) = i=1 li dan src(Kn∗ ) = i=1 li maka rc(Kn∗ ) = Pn ∗ src(Kn ) = i=1 li . Berikut diberikan ilustrasi untuk graf thorn dari graf lengkap dengan n = 4, pada Gambar 3 terlihat bahwa rc(K4∗ ) = src(K4∗ ) = 16.
Gambar 3. rc(K4∗ ) = src(K4∗ ) = 16
Teorema berikut menyajikan bilangan rainbow connection untuk graf thorn dari graf lingkaran. Pada teorema berikut akan ditinjau graf thorn untuk setiap li ≥ n (i ∈ {1, · · · , n}). Teorema 2.5. [7] Untuk n ≥ 4 dan li ≥ n, berlaku n X n rc(Cn∗ ) = src(Cn∗ ) = d e + li . 2 i=1
Bukti. Perhatikan Gambar 4. Untuk n ≥ 4, perhatikan bahwa lingkaran Cn dengan n titik dan untuk setiap i dengan 1 ≤ i ≤ n, misalkan ei = vi vi+1 . Misalkan c sebagai sisi-coloring dari Cn
Bilangan Rainbow Connection untuk Beberapa Graf Thorn
69
Gambar 4. Graf C4∗ .
sebagai berikut: c(ei ) =
i, untuk 1 ≤ i ≤ d n2 e, n i − d 2 e, untuk d n2 e + 1 ≤ i ≤ n.
Karena warna dari sisi thorn harus berbeda, maka berlaku bahwa rc(Cn∗ ) ≤ d n2 e + Pn i=1 li . Pn Selanjutnya, akan ditunjukkan bahwa rc(Cn∗ ) ≥ d n2 e + i=1 li , asumsikan P n berlawanan sehingga rc(Cn∗ ) ≤ d n2 e + i=1 li − 1. Misalkan c∗ adalah rainbow Pn n (d 2 e + i=1 li − 1)-coloring dari Cn∗ . Asumsikan bahwa c∗ (ei ) = c(ei ) maka terdapat paling sedikit dua sisi thorn dengan warna yang sama. Sebaliknya, jika Pn c∗ (vi uij ) = c(vi uij ) maka (d n2 e + i=1 li − 1)-coloring dari Cn∗ memberikan d n2 e − 1 warna yang berbeda sedangkan sisa n sisi dari Cn bukanlah sebuah rainbow coloring. Pn Karena itu, nyatakan sebagai rc(Cn∗ ) = d n2 e + i=1 li . Pn Selanjutnya, akan ditunjukkan bahwa src(Cn∗ ) = d n2 e + i=1 li . Karena diam(Cn ) = d n2 e dan pewarnaan dari sisi thorn haruslah berbeda, maka daPn pat simpulkan bahwa src(Cn∗ ) ≤ d n2 e + i=1 li . Selanjutnya, akan ditunjukkan P n bahwa src(Cn∗ ) ≥ d n2 e + i=1 li . Asumsikan berlawanan sehingga src(Cn∗ ) ≤ P Pn n d n2 e + i=1 li − 1. Misalkan c1 adalah rainbow (d n2 e + i=1 li − 1)-coloring dari Cn∗ . Asumsikan bahwa c1 (ei ) = c(ei ) maka terdapat paling sedikit dua sisi thorn dengan warna yang sama. Asumsikan bahwa c1 (uij ) = c(umn )(i 6= m ∈ {1, 2, · · · , n}), maka tidak terdapat uij vi − vm umn geodesic pada Cn∗ . Similar untuk pembuktian dari bilangan rainbow connection, asumsikan bahwa c1 (vi uij ) = c(vi uij ) maka ini merupakan kontradiksi dari src(Cn ) = d n2 e. Pn Pn Akibatnya, karena rc(Cn∗ ) = d n2 e + i=1 li dan src(Cn∗ ) = d n2 e + i=1 li maka P n rc(Cn∗ ) = src(Cn∗ ) = d n2 e + i=1 li . Berikut diberikan ilustrasi untuk graf thorn dari graf lingkaran dengan n = 4, pada Gambar 5 terlihat bahwa rc(C4∗ ) = src(C4∗ ) = 18. Teorema berikut menyajikan bilangan rainbow connection untuk graf thorn dari graf barbel. Pada teorema berikut akan ditinjau graf thorn untuk setiap li ≥ 2n (i ∈ {1, · · · , 2n}).
70
Melvi Muchlian
Gambar 5. Graf C4∗ .
Teorema 2.6. ♦ Untuk n ≥ 2 dan li ≥ 2n, berlaku rc(Bn∗ ) = src(Bn∗ ) = 3 +
2n X
li .
i=1
Bukti. Perhatikan bahwa uij adalah thorn dari titik vi (i ∈ {1, · · · , 2n}, j ∈ {1, · · · , li }). Perhatikan Gambar 6.
Gambar 6. Graf B4∗ .
P2n Terlebih dahulu akan ditunjukkan bahwa rc(Bn∗ ) ≤ 3 + i=1 li . Karena semua path dari ui1 j1 ke ui8 j2 perlu melalui sisi ui1 j1 vi1 , vi8 ui8 j2 , ini jelas bahwa warna dari sisi vi uij dimana (i ∈ {1, · · · , 2n}, j ∈ {1, · · · , li }) haruslah berbeda. Dengan kata lain, ini merupakan syarat perlu untuk rainbow connectivity suatu graf. Oleh karena itu, dalam pewarnaan ini warnai semua sisi thorn vi uij dengan c(vi uij ) = j (i) dimana j (i) , i ∈ {1, · · · , 2n}, j ∈ {1, · · · , li } terlebih dahulu sebagai kode pewarnaan dari sisi graf. Warnai sisi lain dengan cara berikut: 1 1, jika e ∈ (Kn ), c(e) = 2, jika e ∈ (Kn2 ), 3, jika e adalah sebuah bridge Hal ini jelas bahwa lintasan dari ui1 j1 vi1 −vi1 vi4 −vi4 vi5 −vi5 vi8 −vi8 ui8 j2 dengan (i ) (i ) pewarnaan j1 1 −1−3−2−j2 8 sedangkan ui1 j1 vi1 −vi1 vi4 −vi4 vi5 −vi5 vi6 −vi6 ui6 j8 (i ) (i ) dengan pewarnaan j1 1 − 1 − 3 − 2 − j8 6 . Semua lintasan dari graf memiliki warna
Bilangan Rainbow Connection untuk Beberapa Graf Thorn
71
yang berbeda. Dengan kata lain, setiap dua titik dari graf Bn∗ merupakan lintasan P2n rainbow connected dengan 3 + i=1 li warna. Jadi, dapat dibangun sebuah rainbow P2n 3 + i=1 li -coloring dari Bn∗ sehingga dapat membuat graf Bn∗ rainbow connected. P2n Ini berarti bahwa rc(Bn∗ ) ≤ 3 + i=1 li . P2n Selanjutnya, akan ditunjukkan bahwa rc(Bn∗ ) ≥ 3 + i=1 li . Asumsikan P 2n berlawanan sehingga rc(Bn∗ ) ≤ 3 + i=1 li − 1. Misalkan c1 adalah rainbow P2n 3+ i=1 li −1-coloring dari Bn∗ . Misalkan bahwa ui1 j1 vi1 dan vi8 ui8 j2 adalah dua sisi dengan warna yang sama, maka lintasan ui1 j1 − ui8 j2 di Bn∗ bukanlah rainbow path. P2n Ini menyebabkan kontradiksi, sehingga haruslah rc(Bn∗ ) ≥ 3 + i=1 li selanjutnya P 2n diperoleh bahwa rc(Bn∗ ) = 3 + i=1 li . Kemudian, akan ditunjukkan bahwa c rainbow coloring adalah strong rainbow coloring. Karena ui1 j1 vi1 − vi1 vi4 − vi4 vi5 − vi5 vi8 − vi8 ui8 j2 adalah lintasan dengan panjang d(ui1 j1 , ui8 j2 ) antara ui1 j1 dan ui8 j2 di Bn∗ , dimana i1 , i4 , , i5 , i8 ∈ {1, · · · , 2n} dan i1 6= i4 6= i5 6= i8 , j1 ∈ {1, · · · , li1 }, j2 ∈ {1, · · · , li8 }, sehingga c rainbow coloring dapat membuat Bn∗ strongly rainbow connected. Dengan kata P2n lain src(Bn∗ ) ≤ 3 + i=1 li . P2n Selanjutnya akan ditunjukkan bahwa rc(Bn∗ ) ≥ 3 + i=1 li . Misalkan tanpa P 2n mengurangi keumuman sehingga src(Bn∗ ) = 3 + i=1 li − 1. Terdapat paling sedikit dua sisi thorn yang berwarna sama, maka rainbow geodesic dari satu thorn dengan yang lainnya tidak ada, sehingga ini kontradiksi. Oleh karena itu src(Bn∗ ) = 3 + P2n i=1 li . P2n P2n Akibatnya, karena rc(Bn∗ ) = 3 + i=1 li dan src(Bn∗ ) = 3 + i=1 li maka P 2n rc(Bn∗ ) = src(Bn∗ ) = 3 + i=1 li .
Berikut diberikan ilustrasi untuk graf thorn dari graf barbel dengan n = 3, pada Gambar 7 terlihat bahwa rc(B3∗ ) = src(B3∗ ) = 39.
Gambar 7. Graf B3∗ .
Teorema berikut menyajikan bilangan rainbow connection untuk graf thorn dari graf lolipop. Pada teorema berikut akan ditinjau graf thorn untuk setiap li ≥ n + m (i ∈ {1, · · · , (n + m)})
72
Melvi Muchlian
Teorema 2.7. ♦ Untuk n ≥ 1, m ≥ 2 dan li ≥ n + m, berlaku rc(L∗m,n ) = src(L∗m,n ) = (n + 1) +
n+m X
li
i=1
Bukti. Perhatikan bahwa uij adalah thorn dari titik vi (i ∈ {1, · · · , m}, j ∈ {1, · · · , li }) dan wij adalah thorn dari sisi xi (i ∈ {1, · · · , n}, j ∈ {1, · · · , li }). Perhatikan Gambar ??.
Gambar 8. Graf L∗5,3 .
Misalkan v1 , v2 , · · · , vm adalah himpunan titik-titik dari graf lengkap Km dan x1 , x2 , · · · , xn adalah himpunan titik-titik dari graf lintasan Pn . Misalkan titik vm dibuat berdekatan dengan x1 pada graf L∗m,n . Sedemikian sehingga ada tepat satu path connecting dari titik xn dan vm dengan panjang (n − 1) + 1 = n. Pn+m Terlebih dahulu akan ditunjukkan bahwa rc(L∗m,n ) ≤ (n + 1) + i=1 li . Karena semua path dari ui1 j1 ke wi3 j2 perlu melalui sisi ui1 j1 vi1 , xi3 wi3 j2 , ini jelas bahwa warna dari sisi vi uij dimana (i ∈ {1, · · · , m}, j ∈ {1, · · · , li }) dan sisi xi wij dimana (i ∈ {1, · · · , n}, j ∈ {1, · · · , li }) haruslah berbeda. Dengan kata lain, ini merupakan syarat perlu untuk rainbow connectivity suatu graf. Oleh karena itu, dalam pewarnaan ini warnai semua sisi thorn vi uij dengan c(vi uij ) = j (i) dimana j (i) , i ∈ {1, · · · , m}, j ∈ {1, · · · , li } dan sisi thorn xi wij dengan c(xi wij ) = j (i) dimana j (i) , i ∈ {1, · · · , n}, j ∈ {1, · · · , li } terlebih dahulu sebagai kode pewarnaan dari sisi graf. Warnai sisi lain dengan cara berikut: n − 1, untuk e ∈ (Pn ), c(e) = n + 1, untuk e ∈ (Km ), n, untuk e adalah sebuah bridge Hal ini jelas bahwa lintasan dari ui1 j1 vi1 −vi1 vi5 −vi5 xi1 −xi1 xi2 −xi2 xi3 −xi3 wi3 j2 (i ) (i ) dengan pewarnaan j1 1 − 4 − 3 − 2 − 1 − j2 3 sedangkan ui2 j1 vi2 − vi2 vi5 − vi5 xi1 − (i ) (i ) xi1 xi2 − xi2 xi3 − xi3 wi3 j3 dengan pewarnaan j1 2 − 4 − 3 − 2 − 1 − j3 3 . Semua lintasan dari graf memiliki warna yang berbeda. Dengan kata lain, setiap dua titik Pn+m dari graf L∗m,n merupakan lintasan rainbow connected dengan (n + 1) + i=1 li
Bilangan Rainbow Connection untuk Beberapa Graf Thorn
73
Pn+m warna. Jadi, dapat dibangun sebuah rainbow (n + 1) + i=1 li -coloring dari L∗m,n sehingga dapat membuat graf L∗m,n rainbow connected. Ini berarti bahwa rc(L∗m,n ) ≤ Pn+m (n + 1) + i=1 li . Pn+m Selanjutnya, akan ditunjukkan bahwa rc(L∗m,n ) ≥ (n + 1) + i=1 li . AsumP n+m sikan berlawanan sehingga rc(L∗m,n ) ≤ (n + 1) + i=1 li − 1. Misalkan c1 adalah Pn+m rainbow (n + 1) + i=1 li − 1-coloring dari L∗m,n . Misalkan bahwa ui1 j1 vi1 dan xi3 wi3 j2 adalah dua sisi dengan warna yang sama, maka lintasan ui1 j1 −wi3 j2 di L∗m,n bukanlah rainbow path. Ini menyebabkan kontradiksi, sehingga haruslah rc(L∗m,n ) ≥ Pn+m Pn+m (n + 1) + i=1 li , selanjutnya diperoleh bahwa rc(L∗m,n ) = (n + 1) + i=1 li . Kemudian, akan ditunjukkan bahwa c rainbow coloring adalah strong rainbow coloring. Karena ui1 j1 vi1 − vi1 vi5 − vi5 xi1 − xi1 xi2 − xi2 xi3 − xi3 wi3 j2 adalah lintasan dengan panjang d(ui1 j1 , wi3 j2 ) antara ui1 j1 dan wi3 j2 di L∗m,n , dimana i1 , i5 ∈ {1, · · · , m} dan i1 6= i5 , i1 , i2 , i3 ∈ {1, · · · , n} dan i1 6= i2 6= i3 , j1 ∈ {1, · · · , li1 }, j2 ∈ {1, · · · , li3 }, sehingga c rainbow coloring dapat membuat Pn+m L∗m,n strongly rainbow connected. Dengan kata lain src(L∗m,n ) ≤ (n + 1) + i=1 li . Pn+m Selanjutnya akan ditunjukkan bahwa src(L∗m,n ) ≥ (n + 1) + i=1 li . Misalkan P n+m tanpa mengurangi keumuman sehingga src(L∗m,n ) = (n+1)+ i=1 li −1. Terdapat paling sedikit dua sisi thorn yang berwarna sama, maka rainbow geodesic dari satu thorn dengan yang lainnya tidak ada, sehingga ini kontradiksi. Oleh karena itu Pn+m src(L∗m,n ) = (n + 1) + i=1 li . Pn+m Akibatnya, karena rc(L∗m,n ) = (n + 1) + i=1 li dan src(L∗m,n ) = (n + 1) + Pn+m Pn+m ∗ ∗ i=1 li . i=1 li maka rc(Lm,n ) = src(Lm,n ) = (n + 1) +
Berikut diberikan ilustrasi untuk graf thorn dari graf lolipop dengan m = 3, n = 2, pada Gambar 9 terlihat bahwa rc(L∗3,2 ) = src(L∗3,2 ) = 28.
Gambar 9. Graf L∗3,2
Teorema berikut menyajikan bilangan rainbow connection untuk graf thorn dari graf tadpole. Pada teorema berikut akan ditinjau graf thorn untuk setiap li ≥ n + m (i ∈ {1, · · · , (n + m)}).
74
Melvi Muchlian
Teorema 2.8. ♦ Untuk n ≥ 1, m ≥ 3 dan li ≥ n + m, berlaku ∗ ∗ rc(Tm,n ) = src(Tm,n )=d
n+m X m e+n+ li 2 i=1
Bukti. Perhatikan bahwa uij adalah thorn dari titik vi (i ∈ {1, · · · , m}, j ∈ {1, · · · , li }) dan wij adalah thorn dari sisi xi (i ∈ {1, · · · , n}, j ∈ {1, · · · , li }). Perhatikan Gambar 10.
∗ . Gambar 10. Graf T6,3
Misalkan v1 , v2 , · · · , vm adalah himpunan titik-titik dari graf lingkaran Cm dan x1 , x2 , · · · , xn adalah himpunan titik-titik dari graf lintasan Pn . Misalkan titik vm ∗ . Maka x1 − x2 − · · · − xn − vm adalah dibuat berdekatan dengan x1 pada graf Tm,n ∗ path dengan panjang n pada graf Tm,n . Sedemikian sehingga ada tepat satu path antara vm dan x1 . Pn+m ∗ Terlebih dahulu akan ditunjukkan bahwa rc(Tm,n ) ≤ dm i=1 li . Karena 2 e+n+ semua path dari ui3 j1 ke wi3 j2 perlu melalui sisi ui3 j1 vi3 , xi3 wi3 j2 , ini jelas bahwa warna dari sisi vi uij dimana (i ∈ {1, · · · , m}, j ∈ {1, · · · , li }) dan sisi xi wij dimana (i ∈ {1, · · · , n}, j ∈ {1, · · · , li }) haruslah berbeda. Dengan kata lain, ini merupakan syarat perlu untuk rainbow connectivity suatu graf. Oleh karena itu, dalam pewarnaan ini warnai semua sisi thorn vi uij dengan c(vi uij ) = j (i) dimana j (i) , i ∈ {1, · · · , m}, j ∈ {1, · · · , li } dan sisi thorn xi wij dengan c(xi wij ) = j (i) dimana j (i) , i ∈ {1, · · · , n}, j ∈ {1, · · · , li } terlebih dahulu sebagai kode pewarnaan dari sisi graf. Warnai sisi lain dengan cara berikut: n − 1, untuk e ∈ (Pn ), c(e) = n, untuk e adalah sebuah bridge Warnai path vm −v1 −v2 −· · ·−vd m2 e dengan pewarnaan n+1, n+2, · · · , n+d m 2e dan warnai sisi path vm − vm−1 − vm−2 − · · · − vd m2 e dengan pewarnaan n + d m e, n + 2 dm e − 1, · · · , n + 2, n + 1 2
Bilangan Rainbow Connection untuk Beberapa Graf Thorn
75
Hal ini jelas bahwa lintasan dari ui3 j1 vi3 − vi3 vi2 − vi2 vi1 − vi1 vi6 − vi6 xi1 − (i ) (i ) xi1 xi2 − xi2 xi3 − xi3 wi3 j2 dengan pewarnaan j1 3 − 6 − 5 − 4 − 3 − 2 − 1 − j2 3 sedangkan ui3 j2 vi3 −vi3 vi4 −vi4 vi5 −vi5 vi6 −vi6 xi1 −xi1 xi2 −xi2 xi3 −xi3 wi3 j1 dengan (i ) (i ) pewarnaan j2 3 −4−5−6−3−2−1−j1 3 . Semua lintasan dari graf memiliki warna ∗ yang berbeda. Dengan kata lain, setiap dua titik dari graf Tm,n merupakan lintasan Pn+m m rainbow connected dengan d 2 e + n + i=1 li warna. Jadi, dapat dibangun sebuah Pn+m ∗ ∗ rainbow d m i=1 li -coloring dari Tm,n sehingga dapat membuat graf Tm,n 2 e+n+ P n+m ∗ rainbow connected. Ini berarti bahwa rc(Tm,n ) ≤ dm i=1 li . 2e+n+ Pn+m m ∗ Selanjutnya, akan ditunjukkan bahwa rc(Tm,n ) ≥ d 2 e + n + i=1 li . AsumP n+m ∗ 1 sikan berlawanan sehingga rc(Tm,n ) ≤ dm i=1 li − 1. Misalkan c adalah 2 e+n+ P n+m ∗ rainbow d m i=1 li − 1-coloring dari Tm,n . Misalkan bahwa ui3 j1 vi3 dan 2e+n+ ∗ xi3 wi3 j2 adalah dua sisi dengan warna yang sama, maka lintasan ui3 j1 −wi3 j2 di Tm,n ∗ bukanlah rainbow path. Ini menyebabkan kontradiksi, sehingga haruslah rc(Tm,n ) ≥ Pn+m Pn+m m ∗ dm i=1 li , selanjutnya diperoleh bahwa rc(Tm,n ) = d 2 e + n + i=1 li . 2e+n+ Kemudian, akan ditunjukkan bahwa c rainbow coloring adalah strong rainbow coloring. Karena ui3 j1 vi3 − vi3 vi2 − vi2 vi1 − vi1 vi6 − vi6 xi1 − xi1 xi2 − xi2 xi3 − xi3 wi3 j2 ∗ adalah lintasan dengan panjang d(ui3 j1 , wi3 j2 ) antara ui3 j1 dan wi3 j2 di Tm,n , dimana i1 , i2 , i3 , i6 ∈ {1, · · · , m} dan i1 6= i2 6= i3 6= i6 , i1 , i2 , i4 ∈ {1, · · · , n} dan i1 6= i2 6= i3 , j1 ∈ {1, · · · , li3 }, j2 ∈ {1, · · · , li3 }, sehingga c rainbow coloring ∗ ∗ ) ≤ strongly rainbow connected. Dengan kata lain src(Tm,n dapat membuat Tm,n P n+m e + n + l . dm i=1 i 2 Pn+m ∗ ) > dm + i=1 li . Misalkan Selanjutnya akan ditunjukkan bahwa src(Tm,n 2 e + nP n+m ∗ tanpa mengurangi keumuman sehingga src(Tm,n ) = dm i=1 li −1. Terdapat 2 e+n+ paling sedikit dua sisi thorn yang berwarna sama, maka rainbow geodesic dari satu thorn dengan yang lainnya tidak ada, sehingga ini kontradiksi. Oleh karena itu Pn+m ∗ ) = dm src(Tm,n i=1 li . 2e+n+ Pn+m m ∗ ∗ Akibatnya, karena rc(Tm,n ) = dm i=1 li dan src(Tm,n ) = d 2 e + n + 2e+n+ Pn+m Pn+m m ∗ ∗ i=1 li maka rc(Tm,n ) = src(Tm,n ) = d 2 e + n + i=1 li . Berikut diberikan ilustrasi untuk graf thorn dari graf tadpole dengan m = 3, n = ∗ ∗ 2, pada Gambar 11 terlihat bahwa rc(T3,2 ) = src(T3,2 ) = 28.
∗ . Gambar 11. Graf T3,2
76
Melvi Muchlian
3. Kesimpulan Pada tulisan ini telah diperoleh bilangan rainbow connection untuk graf thorn dari graf lengkap dan graf lingkaran. Selanjutnya diperoleh bilangan rainbow connection untuk graf thorn dari graf barbel, graf lolipop, dan graf tadpole. 4. Ucapan Terima Kasih Penulis mengucapkan terima kasih kepada Bapak Prof. Dr. Syafrizal Sy, Bapak Dr. Muhafzan yang telah memberikan masukan dan saran, sehingga tulisan ini dapat diselesaikan dengan baik. Penulis juga mengucapkan terima kasih kepada Ibu Dr. Lyra Yulianti, Bapak Dr. Admi Nazra, Bapak Dr. Jenizon sehingga paper ini dapat dipublikasikan. Daftar Pustaka [1] Bondy, J.A. dan U.S.R. Murty. 2008. Graph Theory. Graduated Texts In Mathematics. Springer. New York. [2] Chartrand, G. dan P. Zhang, 2005. Introduction to Graph Theory, McGraw-Hill International Editions, Singapore. [3] Chartrand, G. dkk, 2008. Rainbow Connection in Graphs, Math. Bohem. 133: 85 – 98. [4] Diestel, R. 2005. Graph Theory. Electronic Edition 3. New York. [5] Ericksen, A. 2007. Graduating Engineer & Computer Careers. A Matter of security, 24-28. [6] Li, X. dan Y. Sun. 2012. Rainbow Connections of Graphs. Springer Briefs in Mathematics. Springer. New York. [7] Liu, Y. dan Z. Wang. 2014. Rainbow Connection Number of the Thorn Graphs. Applied Mathematical Sciences 8: 6373 – 6377.