Rainbow Connection Number of Special Graph and Its Operations

Rainbow Connection Number of Special Graph and Its Operations Artanty Nastiti, Dafik CGANT-University of Jember Department of Mathematics Education FKIP University of Jember, nastitiartanty02, [email protected] Abstract Let G be a simple graph. An edge-coloring of a graph G is rainbow connected if, for any two vertices of G, there are k internally vertex-disjoint paths joining them, each of which is rainbow and then a minimal numbers of color G is required to make rainbow connected. The rainbow connection numbers of a connected graph G, denoted rc(G). In this paper we will discuss the rainbow connection number rc(G) Jfor some special graph and its P rn , tensor product of P2 N operations, namely crown product of P2 Wn . Kata Kunci : Edge-colouring, Rainbow Connection, Spesial Graph, Graphs Operations.

Introduction Perkembangan teori graf saat ini tidak hanya secara teoritis, tetapi juga secara aplikatif seperti dalam ilmu jaringan komunikasi, transportasi, ilmu komputer, musik, dan ilmu-ilmu lainnya lihat [1], [2], [5], [7], [8]. Salah satu topik yang dipelajari dalam teori graf adalah rainbow connection. Konsep rainbow connection pada graf pertama kali diperkenalkan pada tahun 2008 oleh Chartrand, Johns, McKeon and Zha. 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 [9], [10], [11], [12]. 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 dimana sisi-sisi yang bertetangga mungkin mempunyai warna yang sama. Suatu jalur disebut rainbow jika tidak terdapat dua sisi pada G yang diwarnai

Nastiti, et.al: Rainbow Connection

145

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. Lihat [3], [4], [6]. Penelitian terkait rainbow connection berkembang cukup pesat. Pada artikel ini akan dipelajari tentang rainbow connection number pada graf khusus J N P rn dan P2 Wn . Beberapa hasil penelitian dan operasinya yaitu graf P2 yang telah dilakukan Syafrizal menghasilkan teorema berikut. Theorem 1 [1] [6] 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

Teorema yang Digunakan Beberapa teorema terkait batas atas dan bawah dari rainbow connection. Theorem 2 [3] Andaikan G adalah graf terhubung dengan order n ≥ 3 dan mempunyai degree sekurang-kurangnya d(G) = 2. Jika G ∈ {K3 , C4 , K4 −e, C5 }, maka rc(G) ≤ n − 3. Theorem 3 [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

Hasil Penelitian Hasil dari penelitian ini didapatkan beberapa teorema terkait rainbow connecJ tion untuk operasi graf P2 P rn .

146


3 Teorema 0.1 Untuk n ≥ 2, rainbow connection number untuk operasi graf J P rn adalah P2 rc(P2

K

P rn ) = 4; untuk n ≥ 3

J P rn adalah graf yang memiliki memiliki Bukti. Operasi graf P2 himpunan titik V = {xi , xi,j ; 1 ≤ i ≤ 2; 1 ≤ j ≤ n} dan himpunan sisi E = {xi xi+1 ; i = 1} ∪ {xi xij ; 1 ≤ i ≤ 2; 1 ≤ j ≤ n} ∪ {xi1 xin ; 1 ≤ i ≤ 2} ∪ {xij xij+1 ; 1 ≤ i ≤ 2; 1 ≤ j ≤ n − 1}. Kemudian order dan sizenya adalah masingmasing p = |V | = 2(1 + n) dan q = |E| = 2(2n + 1) − 1. Berdasarkan Teorema J J J 3 dinyatakan bahwa k(P¯2 P rn ) ≤ rc(P2 P rn ) ≤ k(P¯2 P rn ) + 1. J J Untuk n ≥ 2 graf P¯2 P rn memiliki diameter 4 maka 4 ≤ rc(P¯2 P rn ) ≤ 5 naJ ¯ mun demikian terbukti bahwa rc(P2 P rn ) = 4. akan diwarnai dengan fungsi berikut: Untuk n ǫ genap   1, e = xi,1 xi,n ; dengan 1 ≤ i ≤ 2      dengan i = 1, j = ganjil; 1 ≤ j ≤ n − 1  1, e = xi xi,j ;     dengan i = 2, j = genap; 2 ≤ j ≤ n  1, e = xi xi,j ; f (e) = 2, e = xi xi,j ; dengan i = 1, j = genap; 2 ≤ j ≤ n    2, e = xi xi,j ; dengan i = 2, j = ganjil; 1 ≤ j ≤ n − 1      3, e = xi,j xi,j+1 ; dengan 1 ≤ i ≤ 2, 1 ≤ j ≤ n − 1     4, e = xi xi+1 ; dengan i = 1 Untuk n ǫ ganjil   1, e = xi,1 xi,n ; dengan 1 ≤ i ≤ 2      1, e = xi xi,j ; dengan i = 1, j = ganjil; 1 ≤ j ≤ n      dengan i = 2, j = genap; 2 ≤ j ≤ n − 1  1, e = xi xi,j ; f (e) = 2, e = xi xi,j ; dengan i = 1, j = genap; 2 ≤ j ≤ n − 1    2, e = xi xi,j ; dengan i = 2, j = ganjil; 1 ≤ j ≤ n      3, e = xi,j xi,j+1 ; dengan 1 ≤ i ≤ 2, 1 ≤ j ≤ n − 1     4, e = xi xi+1 ; dengan i = 1 J J Jelas bahwa f : E(P2 P rn ) → {1, 2, 3, 4} karena rc(P2 P rn ) ≤ 4. J Maka, rc(P¯2 P rn ) = 4.

2

3 Teorema 0.2 Untuk n ≥ 4, rainbow connection number untuk operasi graf N P2 Wn adalah

147


rc(P2

O

n Wn ) = ⌈ ⌉; untuk n ≥ 4 2

N Wn adalah graf yang memiliki memiliki himBukti. Operasi graf P2 punan titik V = {P, xj ; 1 ≤ j ≤ 2, yi ; 1 ≤ i ≤ n} dan himpunan sisi E = {xj xj+1 ; j = 1}∪{xj yi ; 1 ≤ j ≤ 2, yi ; 1 ≤ i ≤ n}∪{P xj ; 1 ≤ j ≤ 2}∪{P xi ; 1 ≤ i ≤ n} ∪ {yi yi+1 ; 1 ≤ i ≤ n − 1} ∪ {yn y1 }. Kemudian order dan sizenya adalah masingmasing p = |V | = n+3 dan q = |E| = 2n+3. Berdasarkan Teorema 3 dinyatakan N N N bahwa k(P¯2 Wn ) ≤ rc(P2 Wn ) ≤ k(P¯2 Wn ) + 1. N N ¯ Untuk n ≥ 4 graf P2 Wn memiliki diameter ⌈ n2 ⌉ maka ⌈ n2 ⌉ ≤ rc(P¯2 Wn ) ≤ N ⌈ n2 ⌉ + 1 namun demikian terbukti bahwa rc(P¯2 Wn ) = ⌈ n2 ⌉, akan diwarnai dengan fungsi berikut.   1, e = xj xj+1 , j = 1; e = P xj ; e = P yi ; e = xj yi ; dengan 1 ≤ i ≤ n, 1 ≤ j ≤ 2     i, e = y y ; dengan 1 ≤ i ≤ ⌈ n2 ⌉ i i+1 f (e) =  i, e = y⌊ n2 ⌋+i y⌊ n2 ⌋+i+1 ; dengan 1 ≤ i ≤ ⌈ n2 ⌉ − 1     ⌊ n ⌋, e = y y n 1

2

Jelas bahwa f : E(P2

⌈ n2 ⌉. Maka, rc(P¯2

N

N

Wn ) → {1, 2, 3, ..., ⌈ n2 ⌉} karena rc(P2

N

Wn ) ≤

Wn ) = ⌈ n2 ⌉.

2

Kesimpulan Pada bagian ini akan diriview kembali rainbow connection number rc(G) pada graf khusus dan operasinya Berdasarkan hasil penelitian diatas, maka kita dapat menyimpulkan bahwa: J • Untuk graf P2 P rn , didapatkan rainbow connection number adalah 4 untuk n ≥ 3

• Untuk graf P2

N

Wn , didapatkan rainbow connection number adalah n ⌈ ⌉ untuk n ≥ 4 2


148

References [1] Gary Chartrand and Ping Zhang. Chromatic Graph Theory. Chapman and Hall, 2008. [2] A.B. Ericksen, A matter of security, Graduating Engineer and Computer Careers, (2007), 24-28. [3] X.Li and Y.Sun, Rainbow connection numbers of complementary graphs, arXiv:1011.4572v3 [math.CO], 2010. [4] X.Li and Y.Sun, Rainbow connections of graphs a survey, arXiv:1101.5747v2 [math.CO], 2011. [5] ] G. Chartrand, G.L. Johns, K.A. McKeon, and P. Zhang, Rainbow connection in graphs, Math. Bohem., 133, No. 2, (2008), 85–98. [6] Sy, Syafrizal, and Estetikasari, Dewi, On Rainbow Connection for Some Corona Graphs, Applied Mathematical Sciences., Vol. 7, No. 100, (2013), 4975–4979. [7] Joseph A. Gallian, A Dynamic Survey of Graph Labeling, University of Minnesota, 1997. [8] Dafik, Structural Properties and Labeling of Graphs. University of Ballarat, 2007. [9] L. Sunil Chandran, Anita Das, D. Rajendraprasad, and N.M. Varma. Rainbow Connection Number and Connected Dominating Sets, arXiv:1010.2296v1, [math.CO], 2010 [10] Ingo Schiermeyer, On Minimally Rainbow k-Connected Graphs, Elsevier B.V. All rights reserved, 2011 [11] Sourav Chakraborty, Eldar Fischer, Arie Matsliah, and Raphael Yuster, Hardness and algorithms for rainbow connection. Journal of Combinatorial Optimization, pages 118, 2009. [12] 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

Rainbow Connection Number of Special Graph and Its Operations

Recommend Documents