Rainbow Connection Number Pada Operasi Graf

Rainbow Connection Number Pada Operasi Graf Arnasyitha Yulianti S, Dafik CGANT-Universitas Jember Program Studi Pendidikan Matematika FKIP Universitas Jember arnasyithays, [email protected] Abstrak An edge-colouring of a graph G is rainbow connected if there are k internally vertex-disjoint paths joining them, with no two edges on the path have the same color. Let G be a simple graph and f be an edge coloring, where f : E(G) → {1, 2, ..., k}, k ∈ N , and the adjacent edges may have the same colour. The rainbow connection numbers of a connected graph G, denoted by rc(G), is a minimal numbers of color G required to make a rainbow connection. This paper discussed rainbow connection for any special graph, namely graph Pn ⊗ H2,2 and graph P3 ⊗ Cn . Keywords : Edge coloring, Rainbow connection, Graph operation.

Pendahuluan Dalam ilmu matematika dan komputer, teori graf adalah studi tentang grafik dan struktur matematika. Graf dalam konteks ini merujuk pada kumpulan simpul dan tepi yang menghubungkan simpul. Graf adalah salah satu objek utama studi pada Matematika Diskrit. Lebih detail lihat [1],[2]. Konsep rainbow connection pada graf pertama kali diperkenalkan pada tahun 2008 oleh Chartrand, Johns, McKeon and Zhang [4]. Konsep ini termotifasi dari informasi dan komunikasi antara suatu agen pemerintah. Departemen Homeland Amerika Serikat yang dibentuk 2003 sebagai respon atas ditemukannya kelemahan transfer informasi setelah serangan teroris 11 September 2001. Suatu informasi membutuhkan perlindungan dikarenakan terhubung langsung ke security negara, sehingga diharuskan juga terdapat prosedur yang memberikan ijin untuk mengakses antara agen-agen pemerintahan. Setiap jalur transfer informasi diperlukan suatu password dan f irewall angka yang cukup besar untuk melindungi informasi dari serangan pengganggu. Sehinggu muncul pertanyaan, berapa angka minimal passowrd dan f irewall yang dibutuhkan setiap dua orang agen saat melakukan jalur transfer informasi, disamping itu juga tidak terjadi pengulangan password dari masing-masing agen. Lebih detail lihat [8]. Situasi tersebut dapat dimodelkan dengan teori graf. Misalkan G adalah graf terhubung nontrivial dengan edge − coloring c : E(G) → {1, 2, 3, ..., n}, n ∈ N lihat [1],[7],[9], dimana sisi-sisi yang bertetangga mungkin mempunyai warna

Arnasyitha, et.al: Rainbow Connection Number Pada Operasi Graf

84

yang sama. Suatu jalur disebut rainbow jika tidak terdapat dua sisi pada G yang diwarnai sama. Sebuah edge − coloring graf G adalah rainbow connected jika sebarang dua titik yang terhubung dihubungkan oleh jalur rainbow. Jelas bahwa jika graf G adalah rainbow connected maka pasti terhubung. Sehingga rainbow connection number dari graf terhubung G, dinotasikan rc(G), sebagai perwanaan minimum yang dibutuhkan untuk membuat graf G rainbow connected. Lebih detail lihat [3],[10], [6] Penelitian terkait rainbow connection berkembang cukup pesat, lihat [11], [12],[13],[14]. Pada artikel ini akan dipelajari tentang rainbow connection number pada beberapa graf khusus dan operasinya, diantara lain graf rc(Pn × H2,2 ) dan graf rc(P3 ⊗ Cn ). Beberapa hasil penelitian yang telah dilakukan Syafrizal [5] menghasilkan teorema berikut. Theorem 1 [5] Andaikan G dan H adalah dua buah graf terhubung,  ∼ ∼    1, untuk G = K1 dan H = Km   K 2, untuk G ∼ = K1 dan H ∼ = Pm dengan 3 ≤ m ≤ 6 rc(G H) = ∼  3, untuk G = K1 dan H ∼ = Pm dengan m ≥ 7     ∼ G = P2 dan H = Km dengan m ≥ 1

Proof. Kita perhatikan keempat kondisi. J Kondisi 1, untuk G ∼ = K1 dan H ∼ = Km . Karena K1 Km adalah juga graf J komplit, maka rc(K1 Km ) = 1. Kondisi 2, untuk G ∼ = K1 dan H ∼ = Pm J dengan 3 ≤ m ≤ 6, maka rc(K1 Km ) = 2. Kondisi 3, untuk (G ∼ = K1 ∼ ∼ ∼ dan H = Km , m ≥ 7) atau (G = P2 dan H = Km ). Untuk G = K1 dan J H ∼ = Km , m ≥ 7 sehingga rc(K1 Km ) = 3. Selanjutnya, karena rc(P2 ) = 1 J dan rc(Km ) = 1, maka jelaslah bahwa rc(P2 Km ) = 3 dimana m ≥ 1. 2

Teorema yang digunakan Teorema terkait batas atas dan bawah dari rainbow connection. Theorem 2 [3] Andaikan G adalah graf terhubung dengan d(G) ≥ 2. Maka (i) jika G adalah interval graph, maka k(G) ≤ rc(G) ≤ k(G) + 1, sedangkan yang lainnya jika G unit interval graph, maka k(G) = rc(G) (ii) jika G adalah AT-free, maka k(G) ≤ rc(G) ≤ k(G) + 3 (iii) jika G adalah sebuah threshold graph, maka k(G) ≤ rc(G) ≤ 3 (iv) jika G adalah chain graph, maka k(G) ≤ rc(G) ≤ 4 (v) jika G adalah sebuah sircular arc graph, maka k(G) ≤ rc(G) ≤ k(G) + 4

Arnasyitha, et.al: Rainbow Connection Number Pada Operasi Graf

85

Hasil Penelitian Hasil dari penelitian ini didapatkan beberapa teorema terkait rainbow connection untuk beberapa graf khusus dan operasinya, seperti Pn ⊗ H2,2 dan P3 ⊗ Cn . 3 Teorema 0.1 Untuk n ≥ 2, rainbow connection number untuk graf (Pn ⊗ H2,2 ) adalah n + 1. Bukti. Graf Pn ⊗H2,2 adalah graf yang memiliki V (Pn ⊗H2,2 ) = {ai , bi , xi , yi ; 1 ≤ i ≤ n} dan E(Pn ⊗ H2,2 ) = {ai ai+1 , bi bi+1 , xi xi+1 , yi yi+1 ; 1 ≤ i ≤ n − 1} ∪ {ai bi , ai yi , bi xi , xi yi ; 1 ≤ i ≤ n}, dengan p = |V | = 4n dan q = |E| = 8n − 4. Berdasarkan Teorema 2 menyatakan bahwa k(Pn ⊗ H2,2 ) ≤ rc(Pn ⊗ H2,2 ) ≤ k(Pn ⊗H2,2 )+1, diamater dari graf Pn ⊗H2,2 = n+1 maka n+1 ≤ rc(Pn ⊗H2,2 ) ≤ n+2 sehingga terbukti bahwa rc(Pn ⊗H2,2 ) ≥ n+1. Graf Pn ⊗H2,2 akan diwarnai dengan fungsi berikut.   1, e = ai yi ; e = bi xi ; 1 ≤ i ≤ n     2, e = a b ; e = x y ; 1 ≤ i ≤ n i i i i f (e) =  j, e = a a ; e = bi bi+1 ; e = xi xi+1 ; e = yi yi+1 ; 1 ≤ i ≤ n − 1; i i+1     3 ≤ j ≤ n+1 Jelas bahwa f : E(Pn ⊗ H2,2 ) → {1, 2, ..., n + 1} karena rc(Pn ⊗ H2,2 ) ≤ n + 1, maka rc(Pn ⊗ H2,2 ) = n + 1. 2 3 Teorema 0.2 Untuk n ≥ 2, rainbow connection number untuk graf (P3 ⊗ Cn ) adalah ⌈ n2 ⌉ + 2. Bukti. Graf P3 ⊗Cn adalah graf yang memiliki V (P3 ⊗Cn ) = {xi yi , zi ; 1 ≤ i ≤ n} dan E(P3 ⊗Cn ) = {xi yi , yi zi ; 1 ≤ i ≤ n}∪{xi xi+1 , yi yi+1 , zi zi+1 ; 1 ≤ i ≤ n − 1}∪ $xn x1 , yn y1 , zn z1 , dengan p = |V | = 4n dan q = |E| = 8n − 4. Berdasarkan Teorema 2 menyatakan bahwa k(P3 ⊗ Cn ) ≤ rc(P3 ⊗ Cn ) ≤ k(P3 ⊗ Cn ) + 1, diamater dari graf P3 ⊗ Cn = ⌈ n2 ⌉ + 2 maka ⌈ n2 ⌉ + 2 ≤ rc(P3 ⊗ Cn ) ≤ n + 3 sehingga terbukti bahwa rc(P3 ⊗ Cn ) ≥ ⌈ n2 ⌉ + 2. Graf P3 ⊗ Cn akan diwarnai

Arnasyitha, et.al: Rainbow Connection Number Pada Operasi Graf

86

dengan fungsi berikut.   i, e = xi xi+1 ; e = yi yi+1 ; e = zi zi+1 ; 1 ≤ i ≤ ⌈ n2 ⌉, n = genap     e = x⌈ n2 ⌉+i x⌈ n2 ⌉+i+1 ; e = y⌈ n2 ⌉+i y⌈ n2 ⌉+i+1 ; e = z⌈ n2 ⌉+i z⌈ n2 ⌉+i+1 ;       1 ≤ i ≤ ⌈ n2 ⌉ − 1, n = genap      e = xi xi+1 ; e = yi yi+1 ; e = zi zi+1 ; 1 ≤ i ≤ ⌈ n2 ⌉ − 1, n = ganjil  f (e) = e = x⌈ n2 ⌉+i−1 x⌈ n2 ⌉+i ; e = y⌈ n2 ⌉+i1 y⌈ n2 ⌉+i ; e = z⌈ n2 ⌉+i−1 z⌈ n2 ⌉+i ;     1 ≤ i ≤ ⌈ n2 ⌉ − 2, n = ganjil      ⌈ n2 ⌉, e = xn x1 ; e = yn y1 ; e = zn z1    n   ⌈ 2 ⌉ + 1, e = xi yi ; 1 ≤ i ≤ n    n ⌈ 2 ⌉ + 2, e = yi zi ; 1 ≤ i ≤ n Jelas bahwa f : E(P3 ⊗ Cn ) → {1, 2, ..., ⌈ n2 ⌉ + 2} karena rc(P3 ⊗ Cn ) ≥ ⌈ n2 ⌉ + 2, maka rc(P3 ⊗ Cn ) = ⌈ n2 ⌉ + 2. 2

Kesimpulan Pada bagian ini akan diriview kembali rainbow connection number rc(G) pada beberapa graf khusus dan operasinya. Berdasarkan hasil penelitian diatas, maka kita dapat menyimpulkan bahwa. Untuk graf Pn ⊗ H2,2 , didapatkan rainbow connection number adalah rc(Pn ⊗ H2,2 ) adalah n + 1 Untuk graf P3 ⊗Cn , didapatkan rainbow connection number adalah rc(P3 ⊗ Cn ) adalah ⌈ n2 ⌉ + 2

Ucapan Terima Kasih Penulis mengucapkan terima kasih kepada dosen pembina mata kuliah yang telah membimbing serta memberikan kritik dan saran sehingga artikel ini bisa selesai dengan baik.

References [1] Gary Chartrand and Ping Zhang. Chromatic Graph Theory. Chapman and Hall, 2008.

Arnasyitha, et.al: Rainbow Connection Number Pada Operasi Graf

87

[2] J.A. Bondy and U.S.R. Murty, Graph Theory (GTM 244, Springer, 2008). [3] X.Li and Y.Sun. 2010, Rainbow connection numbers of complementary graphs, arXiv:1011.4572v3 [math.CO] [4] G. Chartrand, G.L. Johns, K.A. McKeon, and P. Zhang, Rainbow connection in graphs, Math. Bohem., 133, No. 2, (2008), 85–98 [5] Sy, Syafrizal, and Estetikasari, Dewi, On the rainbow connection for some corona graphs, Applied Mathematical Sciences., Vol. 7, No. 100, (2013), 4975– 4979. [6] I. Schiermeyer, Rainbow connection in graphs with minimum degree three, IWOGA 2009, LNCS 5874 (2009) 432-437. [7] Dafik. Structural properties and labeling of graphs. Diss. University of Ballarat, 2007. [8] A.B. Ericksen, A matter of security, Graduating Engineer and Computer Careers, (2007), 24-28. [9] Joseph A. Gallian, A Dynamic Survey of Graph Labeling, University of Minnesota, 1997. [10] X.Li and Y.Sun, Rainbow connections of graphs a survey, arXiv:1101.5747v2 [math.CO], 2011. [11] L. Sunil Chandran, Anita Das, D. Rajendraprasad, and N.M. Varma. Rainbow Connection Number and Connected Dominating Sets, arXiv:1010.2296v1, [math.CO], 2010 [12] Ingo Schiermeyer, On Minimally Rainbow k-Connected Graphs, Elsevier B.V. All rights reserved, 2011 [13] Sourav Chakraborty, Eldar Fischer, Arie Matsliah, and Raphael Yuster, Hardness and algorithms for rainbow connection. Journal of Combinatorial Optimization, pages 118, 2009. [14] M. Basavaraju, L. Sunil Chandran, D. Rajendraprasad, and A. Ramaswamy, Rainbow Connection Number of Graph Power and Graph Products, arXiv:1104.4190v2 [math.CO], 2011