BATAS ATAS RAINBOW CONNECTION NUMBER PADA GRAF DENGAN KONEKTIVITAS 3

Jurnal Matematika UNAND Vol. 5 No. 4 Hal. 45 – 53 ISSN : 2303–2910 c

Jurusan Matematika FMIPA UNAND

BATAS ATAS RAINBOW CONNECTION NUMBER PADA GRAF DENGAN KONEKTIVITAS 3 PRIMA RESA PUTRI Program Studi Magister Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Andalas, Kampus UNAND Limau Manis Padang, Indonesia, email : [email protected]

Abstrak. Suatu graf G dikatakan bersifat rainbow connected apabila setiap dua titik di G dihubungkan oleh suatu lintasan (path) yang setiap sisinya memiliki warna yang berbeda. Rainbow Connection Number dari suatu graf G, dinotasikan rc(G), adalah jumlah terkecil pewarnaan yang diperlukan untuk membuat G bersifat rainbow connected. Pada makalah ini akan dikaji kembali tentang batas atas bilangan rainbow connection untuk graf dengan konektifitas 3, seperti yang telah dibahas dalam [7]. Kata Kunci: Rainbow connection number, konektifitas

1. Pendahuluan Teori graf muncul pada tahun 1736 ketika Euler mengemukakan masalah Jembatan Konigsberg. Pada awalnya graf diterapkan dalam penyelesaian masalah rute terpendek, namun seiring perkembangan zaman dan kemajuan teknologi, aplikasi teori graf telah merambah ke aneka disiplin ilmu dan membantu memudahkan orang untuk menyelesaikan beberapa permasalahan. Penggunaan graf ditekankan untuk memodelkan persoalan. Teori graf juga sangat berguna untuk mengembangkan modelmodel yang terstruktur dalam berbagai situasi. Salah satu teori yang berkembang pesat dalam kajian teori graf adalah konsep rainbow connection. Konsep rainbow connection pada awalnya diperkenalkan oleh Chartrand pada tahun 2006 [2]. Suatu lintasan dikatakan rainbow path jika tidak ada dua sisi dalam lintasan terebut yang memiliki warna sama. Graf G dikatakan rainbow connected jika setiap dua titik yang berbeda dihubungkan oleh rainbow path. Dalam hal ini, pewarnaan graf G disebut rainbow coloring. Jika ada sebanyak k warna yang digunakan, maka pewarnaannya disebut rainbow k-coloring. Minimum dari banyak warna yang dibutuhkan sedemikian sehingga suatu graf menjadi rainbow connected disebut dengan rainbow connection number, dinotasikan rc(G). Jika untuk setiap dua titik u dan v di G, panjang rainbow path pada graf G sama dengan d(u, v), yaitu jarak antara kedua titik tersebut, maka graf G dikatakan strong rainbow connected. Dalam hal ini, pewarnaan graf G disebut strong rainbow coloring, dan rainbow path dikatakan geodesic. Jika ada sebanyak k warna yang digunakan, maka pewarnaannya disebut strong rainbow k-coloring. Minimum dari banyak warna yang dibutuhkan sedemikian sehingga suatu graf menjadi strong rainbow connected disebut dengan strong rainbow connection number, dinotasikan src(G). 45

46

Prima Resa Putri

Dapat dilihat bahwa untuk suatu graf terhubung tak trivial G dengan banyak sisi m, berlaku diam(G) < rc(G) < src(G) < m.

(1.1)

Dalam kajian ini akan dibahas tentang batas atas pada graf terhubung sederhana yang tak trivial dengan 3-vertex connected, seperti yang telah dibahas dalam [7]. 2. Beberapa Konsep dalam Rainbow Connection Berikut disajikan kembali proposisi yang membahas tentang graf G dengan ukuran m yang mempunyai nilai rc(G) dan src(G) 1, 2 dan m. Proposisi 2.1. [3] Misalkan G suatu graf terhubung tak trivial berukuran m. Maka berlaku (1) rc(G) = src(G) = 1 jika dan hanya jika G suatu graf lengkap, (2) rc(G) = 2 jika dan hanya jika src(G) = 2, (3) rc(G) = src(G) = m jika dan hanya jika G suatu graf pohon. Bukti. (1) Jika pada graf lengkap G diberikan 1 warna untuk tiap sisi-sisinya, maka untuk setiap dua titik u dan v di G terdapat rainbow 1-coloring yang juga merupakan u − v geodesic. Jadi G merupakan rainbow 1-coloring dan strong rainbow 1coloring sehingga rc(G) = src(G) = 1. Jika rc(G) = src(G) = 1 tidak ada dua titik yang tidak bertetangga maka haruslah G merupakan graf lengkap. (2) Jika rc(G) = 2, ini berarti G memiliki suatu rainbow 2-coloring yang mengakibatkan setiap dua titik yang tidak bertetangga dihubungkan oleh suatu rainbow path dengan panjang 2, maka haruslah src(G) ≥ 2. Karena lintasan tersebut merupakan geodesic, jadi tidak mungkin src(G) > 2 maka src(G) = 2. Sebaliknya, asumsikan src(G) = 2. berdasarkan (1) haruslah rc(G) ≤ 2. karena G bukan merupakan graf lengkap, sehingga rc(G) = 2. (3) Andaikan G bukan graf pohon. Maka G memiliki suatu lingkaran C : v1 , v2 , · · · , vk , v1 dimana k ≥ 3. Maka (m − 1)-coloring terhadap sisi-sisi G yang memberikan 1 untuk sisi v1 v2 dan v2 v3 , dan memberikan (m − 2) buah warna berbeda dari himpunan warna {2, 3, · · · , m − 1} untuk m − 2 sisi tesisa di G adalah rainbow coloring. Jadi, rc(G) ≤ m − 1. Selanjutnya misalkan G adalah graf pohon dengan ukuran m. Asumsikan bahwa rc(G) ≤ m − 1. Misalkan c adalah suatu minimum rainbow coloring di G. Maka terdapat sisi e dan f sehingga c(e) = c(f ). Asumsikan tanpa mengurangi perumuman, bahwa e = uv dan f = xy, dan G memiliki suatu u − y path u, v, · · · , x, y. Maka tidak terdapat rainbow u − y path di G, kontradiksi dengan G mempunyai rainbow coloring. Jadi, haruslah G adalah graf pohon berukuran m. Proposisi 2.2. [3] Misalkan Cn adalah graf lingkaran dengan banyak titik n, dimana n ≥ 4 maka rc(Cn ) = src(Cn ) = d n2 e.

Batas Atas Rainbow Connection Number Pada Graf Dengan Konektivitas 3

47

Bukti. Misalkan terdapat lingkaran Cn dengan V (Cn ) = {v1 , v2 , · · · , vn , v1 } dan E(Cn ) = {vi vi+1 |1 ≤ i ≤ n} ∪ {v1 vn } untuk setiap i di G dengan 1 ≤ i ≤ n. Pandang dua kasus berikut. Kasus 1. n adalah genap. Misalkan n = 2k untuk bilangan bulat k ≥ 2 maka src(Cn ) ≥ rc(Cn ) ≥ diam(Cn ) = k. Konstruksikan pewarnaan sisi c0 dari Cn sebagai berikut. i, untuk 1 ≤ i ≤ k; c0 (ei ) = i − k, untuk k + 1 ≤ i ≤ n. Berdasarkan Pertidaksamaan 1.1, maka berlaku rc(Cn ) ≤ src(Cn ) ≤ k, sehingga rc(Cn ) = src(Cn ) = k. Kasus 2. n adalah ganjil. Misalkan n = 2k + 1 untuk bilangan bulat k ≥ 2. Definisikan pewarnaan sisi c1 dari Cn dengan i, untuk 1 ≤ i ≤ k + 1; c0 (ei ) = i − k − 1, untuk k + 2 ≤ i ≤ n. Karena c1 adalah strong rainbow (k +1)-coloring dari Cn maka rc(Cn ) ≤ src(Cn ) ≤ k +1. Karena rc(Cn ) ≥ diam(Cn ) = k maka rc(Cn ) = k atau rc(Cn ) = k +1. Klaim bahwa rc(Cn ) = k + 1. Asumsikan dengan kontradiksi bahwa rc(Cn ) = k. Misalkan c0 adalah suatu rainbow k-coloring dari Cn dan misalkan P adalah lintasan dari u ke v pada Cn . Maka P adalah lintasan u-v geodesic di Cn adalah rainbow path, sementara u-v path lainnya di Cn bukan rainbow path karena memiliki panjang k+1. Tanpa mengurangi perumuman, misalkan c0 (vk+1 vk+2 ) = k. Pandang titik-titik v1 , vk+2 dan vk+2 . Karena lintasan v1 − vk+1 geodesic P : v1 , v2 , · · · , vk+1 adalah rainbow path dan lintasan v1 −vk+2 geodesic, Q : v1 , vn , · · · vn−1 , vk+2 adalah rainbow path, maka beberapa sisi di P dan Q diwarnai dengan warna k. Karena v2 − vk+2 geodesic, v2 , v3 , · · · , vk+2 adalah rainbow path maka c0 (v1 v2 ) = k. Dengan cara yang sama, vn − vk+1 geodesic, vn , vn−1 , vn−2 · · · vk+1 sehingga c0 (vn v1 ) = k diperoleh c0 (v1 v2 ) = c0 (vn v1 ) = k. Ini berarti, tidak terdapat raibow v2 − vn path di G. Ini kontradiksi dengan c0 adalah suatu rainbow k-coloring dari Cn . Jadi, haruslah rc(Cn ) = src(Cn ) = k + 1. Misalkan G adalah suatu graf dengan n titik. Himpunan k-vertex cut adalah vertex cut dengan k elemen. Sebelum membuktikan Teorema 2.4, diberikan Lema 2.3 berikut. Lema 2.3. [7] (Fan Lemma) Jika G adalah graf k-connected dengan x ∈ V (G), dan Y ⊆ V (G) − {x} sedemikian sehingga |Y | ≥ k, maka G memuat suatu k − f an dari x ke Y , yaitu ada sebuah k-Internally disjoint (x, Y )-path yang mana titik internalnya berbeda di Y . Bukti. Misalkan G adalah suatu graf k-connected dengan S adalah vertex-cut minimal. Misalkan terdapat titik x ∈ V (G). Misalkan Y adalah subhimpunan titik dari

48

Prima Resa Putri

V (G) sedemikian sehingga |Y | ≥ k. Karena |Y | ≥ k maka pilih Y 0 ⊆ Y dengan |Y 0 | = k titik. Misalkan Y 0 = {y10 , y20 , · · · , yk0 }. Konstruksi graf G0 dari graf G dengan menambahkan satu titik y, kemudian menghubungkan y ke setiap titik di Y 0 . Karena G adalah graf k-connected maka jelas bahwa G0 adalah juga graf k-connected . Akibatnya, antara titik x dan titik y di G terdapat k-internally disjoint path. Jadi, karena |Y 0 | = k maka terdapat k-fan dari x ke setiap titik di Y 0 . Sebagai ilustrasi perhatikan gambar berikut:

Gambar 1. Ilustrasi 1

Teorema berikut mengkaji tentang batas atas rainbow connection number untuk graf G yang mempunyai sifat 3-vertex connected, seperti yang telah dibahas dalam [7]. Teorema 2.4. [7] Jika G adalah graf sederhana yang bersifat 3-vertex connected dengan n titik maka rc(G) ≤ 3(n + 1)/5. Bukti. Misalkan G adalah graf 3-vertex connected dengan n titik dan misalkan H merupakan subgraf terhubung maksimal dari G dengan h titik sedemikian sehingga berlaku rc(H) ≤ 3h/5 − 1/5. Misalkan G dengan n = 3. Karena G adalah graf 3-vertex connected, maka G memuat cycle. Jika G memuat suatu cycle C3 maka H adalah C3 karena H adalah subgraf terhubung maksimal. Sehingga memenuhi rc(C3 ) = 1 < 8/5 = 9/5 − 1/5 = 3 × 3/5 − 1/5 = 3h/5 − 1/5. Misalkan G memuat Ck dimana (k ≥ 4) dan (k 6= 5) sebagai subgraf, maka ambil H = Ck karena memenuhi rc(Ck ) = dk/2e ≤ 3k/5 − 1/5. Misalkan G memuat suatu cycle C5 , maka ambil H 0 sebagai graf dengan menambahkan satu sisi baru diluar C5 untuk C5 sehingga h = 6. Maka diperoleh: rc(H 0 ) = 3 < 17/5 = 18/5 − 1/5 = 3 × 6/5 − 1/5 = 3h/5 − 1/5.


49

Klaim bahwa h ≥ n−3. Dengan kontradiksi, misalkan h < n−3. Misalkan terdapat empat titik berbeda diluar H misalkan x1 , x2 , x3 , x4 . Dengan Lema Fan, maka untuk setiap titik di x1 , x2 , x3 , x4 terdapat 3-fan ke H. Sebagai ilustrasi perhatikan Gambar 2.


Asumsikan bahwa x1 , x2 , x3 , x4 memiliki 3 titik yang bertetangga di H. Misalkan fij adalah sisi yang terkait dengan titik xi , j = 1, 2, 3. Tambahkan x1 , x2 , x3 , x4 ke H = {v1 , v2 , v3 } membentuk subgraf H 0 . Jadi V (H 0 ) = {v1 , v2 , v3 } ∪ {x1 , x2 , x3 , x4 } sehingga |V (H 0 )| = h + 4 titik. Gunakan warna 1 dan 2 untuk mewarnai 12 sisi. Berikan warna 1 ke sisi fi1 untuk i = 1, 2, 3 dan warna 2 untuk 9 sisi lainnya. Maka H 0 adalah rainbow connected dengan dua warna baru. Sebagai ilustrasi perhatikan Gambar 3.


Sehingga diperoleh 3(h + 4) 1 3h 1 − +2< − , 5 5 5 5 yang kontradiksi dengan h + 4 < n. Maka asumsi bahwa x1 , x2 , x3 , x4 bertetangga dengan sembarang titik di H tidak berlaku. Akibatnya, jika terdapat empat titik di rc(H 0 ) ≤ rc(H) + 2 ≤

50

Prima Resa Putri

luar H, maka sekurang-kurangnya terdapat satu titik, sebut x ∈ {x1 , x2 , x3 , x4 } di luar H yang mempunyai internally disjoint path x ke H dengan d(x, a) ≥ 2 untuk suatu a ∈ H. Karena x 6∈ H, maka terdapat 3-fan dari x ke H. Misalkan P, Q, R adalah tiga internally disjoint path yang menghubungkan x ke H. Misalkan P menghubungkan titik-titik x dan c, Q menghubungkan titik a, u1 , u2 , · · · , us , x dan R menghubungkan titik-titik x, v1 , v2 , · · · , vt , b untuk suatu a, b, c ∈ H dan us , ut 6∈ H. Perhatikan ilustrasi pada Gambar 4.


Asumsikan t ≥ s untuk t ≥ 1, dan s+t ≥ 3. Dimana t adalah v1 , v2 , · · · , vt dan s adalah u1 , u2 , · · · , us . Misalkan P adalah lintasan yang menghubungkan titik-titik v1 , v2 , · · · , vt , x, u1 , u2 , · · · , us . Jika v1 , v2 , · · · , vt , x, u1 , u2 , · · · , us ditambahkan ke H, maka diperoleh subgraf diperluas, sebut H 0 dengan h + s + t + 1 titik. Jika s + t genap, maka s + t + 2 sisi pada lintasan P yang menghubungkan titiktitik a, u1 , u2 , · · · , us , x, v1 , v2 , · · · , vt , b diwarnai dengan (s + t + 2)/2 warna yang tidak terdapat pada H dengan cara mewarnai (s + t + 2)/2 sisi pertama lintasan P diberi warna yang tidak terdapat pada H dan (s + t + 2)/2 sisi berikutnya diberi warna yang terdapat pada (s + t + 2)/2 sisi sebelumnya. Sisi e0 diberi sebarang warna yang telah muncul di H. Dengan demikian H 0 adalah rainbow connected. Jika s + t ganjil, maka s + t + 2 pada lintasan yang menghubungkan titik-titik a, u1 , u2 , · · · , us , x, v1 , v2 , · · · , vt , b diwarnai dengan (s + t + 1)/2 warna yang tidak terdapat pada H dengan cara mewarnai (s + t + 1)/2 sisi pertama pada lintasan diberi warna yang tidak terdapat pada H, dan (s + t + 1)/2 sisi berikutnya diberi warna seperti (s + t + 1)/2 sisi sebelumnya. Dengan demikian H 0 adalah rainbow connected. Sehingga diperoleh rc(H 0 ) ≤ rc(H)+d(s+t+2)e/2 ≤ 3h/5−1/5+d(s+t+2)e ≤ 3(h+s+t+1)/5−1/5, yang kontradiksi dengan h + t + s + 1 < n. Jadi haruslah 1 ≤ s + t ≤ 2. Pandang beberapa kasus berikut. Kasus 1. s + t = 2 dan Q = au1 x, R = xv1 b Karena setidaknya ada 4 titik diluar H, terdapat paling sedikit satu titik yang berbeda dari x, u1 dan v1 sebut dengan x1 . Dengan memilih x tidak ada (x1 , x)path, (x1 , u1 )- path, dan (x1 , v1 )-path tanpa menggunakan sembarang titik di H


51

kecuali hanya terdapat satu path yang panjangnya 2 menghubungkan x ke H melalui x1 , katakanlah S = xx1 c dengan c ∈ H. Dalam hal ini, kita hanya memperhatikan tiga path yaitu Q, R dan S. Tambahkan titik x, u1 , v1 dan x1 ke H membentuk subgraf H 0 dengan h+4 titik. Dengan memberi warna 1 ke sisi au1 , bv1 dan warna 2 ke sisi u1 x, cx1 dan warna yang sudah ada di H ke sisi v1 x, xx1 , jadi kontradiksi dengan pertidaksamaan: 3h 1 3(h + 4) 1 − +2< − . 5 5 5 5 Dengan Lema Fan, terdapat tiga internally disjoint path yaitu (x1 , H)-jalur P 0 , Q0 , S 0 . Dengan memilih x, panjang dari P 0 , Q0 , S 0 hanya memiliki empat kemungkinan yaitu: Subkasus 1.1 Panjang P 0 = 1 dengan P 0 = e00 , panjang Q0 = 1 dengan Q0 = e01 , panjang R0 = 1 dengan R0 = e02 . Tambahkan x, u1 , v1 dan x1 ke H dan membentuk graf H 0 dari jumlah titik h + 4. Berikan warna 1 pada au1 , e0 , xv1 , e00 , e01 dan warna 2 pada u1 x, v2 b, e02 . Sehingga kontradiksi dengan pertidaksamaan: rc(H 0 ) ≤ rc(H) + 2 ≤

3(h + 4) 1 3h 1 − +2< − . 5 5 5 5 Subkasus 1.2 Panjang P 0 = 1 dengan P 0 = e00 , panjang Q0 = 1 dengan Q0 = e01 , panjang R0 dengan R0 = x1 v10 b0 . Tambahkan x, u1 , v1 , x1 dan v10 pada H dan membentuk graf yang lebih besar dari H 0 dimana h + 5. Warnai sisi 1 pada au1 , e0 , xv1 , e00 , x1 v10 , warna 2 pada u1 x, v1 b, e01 dan warna 3 pada v10 b0 . Sehingga kontradiksi dengan pertidaksamaan: rc(H 0 ) ≤ rc(H) + 2 ≤

3(h + 5) 1 3h 1 − +3< − . 5 5 5 5 0 0 0 Subkasus 1.3 Panjang P = 1 dengan P = e0 , Panjang Q0 = 2 dengan Q0 = a0 u01 x1 , panjang R0 = 2 dengan R0 = x1 v10 b0 . Tambahkan x, u1 , v1 , x1 , u01 dan v10 pada H dan membentuk graf yang lebih besar dari H 0 dimana h + 6. Berikan warna 1 pada au1 , e0 , xv1 , a0 u01 , x1 v10 , warna 2 pada u1 x, v1 b, u01 x1 dan warna 3 pada e00 , v10 b0 . Sehingga kontradiksi dengan pertidaksamaan: 3(h + 6) 1 3h 1 − +3< − . rc(H 0 ) ≤ rc(H) + 3 ≤ 5 5 5 5 Subkasus 1.4 Panjang P 0 = 1 dengan P 0 = e00 , panjang Q0 = 2 dengan Q0 = e01 , panjang R0 = 3 dengan R0 = x1 v10 v20 b0 . Tambahkan x, u1 , v1 , x1 , u01 dan v20 pada H dan membentuk graf yang lebih besar dari H 0 dimana h + 6. Warnai sisi 1 pada v10 v20 , warna 2 pada x01 v10 dan warna 3 pada e00 , e01 , v20 b0 . Sehingga kontradiksi dengan pertidaksamaan: rc(H 0 ) ≤ rc(H) + 3 ≤

3h 1 3(h + 6) 1 − +3< − . 5 5 5 5 Kasus 2. s + t = 2 dan Q = ax dan R = xv1 v2 b. Dari Lema Fan, terdapat tiga disjoint (v1 , H). Jadi terdapat paling sedikit satu (v1 , H)-path S yang baru kecuali path v1 xa dan v1 v2 b. Dengan memilih x panjang rc(H 0 ) ≤ rc(H) + 3 ≤

52

Prima Resa Putri

P3 haruslah paling banyak dua. Jika S mempunyai panjang 2, maka berlaku Kasus 1. Panjang S adalah 1, sehingga path axv1 , v1 v2 b dan S membangun struktur yang sama pada kasus 1. Kasus 3. s + t = 1. Karena t ≥ s maka t = 1. Asumsikan Q = e1 dan R = xv1 b. Jadi terdapat paling sedikit dua titik berbeda diluar H yang berbeda dari x dan v1 sebut x1 dan x2 . Sama halnya untuk i = 1, 2 tidak ada (xi , x)-path dan (xi , v1 )-path tanpa menggunakan sembarang titik di H. Jadi Terdapat juga tiga disjoint (x1 , H)-path yaitu P 0 , Q0 , R0 dan internally disjoint (x2 , H)-path yaitu P 00 , Q00 , R00 . Jika semua path ini mempunyai panjang satu, maka tambahkan x, v1 , x1 dan x2 ke H, dan membentuk graf H 0 mempunyai titik h + 4. Dengan memberi warna 1 ke sisi e0 , xv1 , P 0 , Q0 , P 00 , Q00 , dan warna 2 ke sisi e1 , v1 b, R0 , R00 sehingga kontradiksi dengan pertidaksamaan: 3(h + 4) 1 3h 1 − +2< − . 5 5 5 5 Tanpa mengurangi perumuman, asumsikan satu dari tiga (x1 , H)-path yaitu P 0 , Q0 , R0 mempunyai panjang 2. Misalkan P 0 = e00 , Q0 = e01 , R0 = x1 v10 b0 . Tambahkan x, v1 , x1 dan v10 ke H, dan membentuk graf 0 H 0 dengan jumlah titik h + 4. Dengan mewarnai 1 ke sisi e0 , e1 , xv1 , v1 b, dan warna 2 ke sisi e00 , e01 , x1 v10 , v10 b0 . Maka 3(h+4) 1 − 15 yang kontradiksi dengan diperoleh rc(H 0 ) ≤ rc(H) + 2 ≤ 3h 5 − 5 +2 < 5 h + 4 < n. Maka asumsi bahwa s + t = 1 seperti yang diuraikan pada Kasus 3 tidak berlaku. Dengan memperhatikan beberapa kasus di atas diperoleh: rc(H 0 ) ≤ rc(H) + 2 ≤

rc(G) ≤ 3(n + 1)/5, Untuk h = n − 3, rc(G) ≤ rc(H) + 2 ≤ 3(h − 3)/5 − 1/5 + 2 < 3(n + 1)/5, Untuk h = n − 2, rc(G) ≤ rc(H) + 2 ≤ 3(h − 2)/5 − 1/5 + 2 = 3(n + 1)/5, Untuk h = n − 1, rc(G) ≤ rc(H) + 1 ≤ 3(h − 1)/5 − 1/5 + 2 < 3(n + 1)/5. 3. Kesimpulan Pada tulisan ini telah dikaji kembali bahwa untuk graf G yang bersifat 3-vertex connected dengan n titik maka berlaku bahwa rc(G) ≤ 3(n + 1)/5. 4. Ucapan Terima Kasih Penulis mengucapkan terima kasih kepada Bapak Prof. Dr. Syafrizal Sy, Ibu Dr. Lyra Yulianti, Bapak Dr. Muhafzan, Bapak Dr. Admi Nazra dan Bapak Dr. Mahdhivan Syafwan yang telah memberikan masukan dan saran sehingga tulisan ini dapat diselesaikan dengan baik. Daftar Pustaka [1] Caro, Y., A. Lev, Y. Roditty, Z Tuza, R. Yuster. 2008. On Rainbow Connection. The Electronic Journal of Combinatorics 15 (57) : 1 – 13


53

[2] Chartrand, G. 2006. Introduction to Graph Theory. McGraw-Hill. Boston. [3] Chartrand, G. 2008. Rainbow Connection in Graphs. Math. Bohem. 133 : 85 – 98. [4] Chandran, L. Sunil, dan Mathew, Roger. 2011. On Rainbow Connection Number and Connectivity. arXiv:1105.5704v1. India. [5] Diestel, R. 2010: Graph Theory, 4nd ed. Springer. New York. [6] Schiermeyer, I. 2008. Rainbow Connection in Graph with Minimum Degree Three. Lecture Notes On Computer Sciences. Springer-Verlag Berlin. 5874: 432 – 437. [7] Li, Xueliang dan Shi, Yongtang. 2010. Rainbow Connection in 3 − connected graphs. arXiv:1010.6131v1. China.

BATAS ATAS RAINBOW CONNECTION NUMBER PADA GRAF DENGAN KONEKTIVITAS 3

Recommend Documents