Rainbow Connection Number of Prism and Product of Two Graphs Randhi N. Darmawan1,2 , Dafik1,3 1 CGANT- University of Jember 2 Department of Mathematics FMIPA University of Jember
[email protected] 3 Department of Mathematics Education FKIP University of Jember,
[email protected] Abstract An edge-colouring 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) for some special graphs and its operations, N namely prism graph Pm,n , antiprism graph APn , tensor product of C3 Ln , joint graph K¯3 +Cn . Key Words : edge-colouring, rainbow connection, graph operation.
Pendahuluan Konsep rainbow connection pada graf pertama kali diperkenalkan pada tahun 2008 oleh Chartrand, Johns, McKeon and Zhang [5]. 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 [2]. 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],[8], dimana sisi-sisi yang bertetangga mungkin mempunyai warna 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. Se-
ð Randhi N. Darmawan., et.al: Rainbow Connection Number
11
hingga 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],[4]. Penelitian terkait rainbow connection berkembang cukup pesat, lihat [9], [10],[11],[12]. Pada artikel ini akan dipelajari tentang rainbow connection number pada beberapa graf khusus dan operasinya, diantara lain graf prisma ¯ 3 +Cn , dan graf tensor product Pn,m , graf antiprisma APn , graf joint product K C3 ⊗ Ln . Beberapa hasil penelitian yang telah dilakukan Syafrizal [6] menghasilkan teorema berikut. Theorem 1 [6] Untuk setiap bilanagn bulat n, rainbow connection number dari graf G adalah rc(G) = 4 dimana G ∼ = Gn dengan n ≥ 4, atau G ∼ = Bn dengan n ≥ 3. Bukti. Kita perhatikan kedua kondisi. Kondisi 1. Untuk G ∼ = Gn dengan n ≥ 4. Misalkan Wn adalah graf yang terdiri atas cycle Cn dengan sebuah titik tambahan yang adjacent ke seluruh titik pada Cn . Sebuah gear graph Gn adalah wheel graph dengan sebuah titik tambahan diantara setiap pasangan titik yang adjacent pada titik cycle Cn terluar, sehingga Gn memiliki |V | = 2n + 1 dan |E| = 3n. Maka jelas Gn memiliki diameter k(Gn ) = 4, sehingga rc(G) ≥ k(Gn ) = 4. Selanjutnya akan ditunjukkan bahwa rc(G) ≤ 4. Berdasarkan V (Gn ) = V (C2n )∪ {v} dimana V (C2n = {v1 , v2 , ...v3 } adalah himpunan titik di C2n . Kemudian akan didefinisikan pewarnaan sisi pada Gn dengan c : E(G) → {1, 2, 3, 4} sesuai fungsi berikut: 1, e = vv4i−3 ; 2, e = vv 4i−1 ; c(e) = 3, e = v4i−3 v4i−2 ; e = v4i v4i+1 4, e = v 4i−2 v4i−1 ; e = v4i−1 v4i
dengan 1 ≤ i ≤ ⌈ n2 ⌉, dengan 1 ≤ i ≤ ⌈ n2 ⌉, dengan 1 ≤ i ≤ ⌈ n2 ⌉, dengan 1 ≤ i ≤ ⌈ n2 ⌉.
Berdasarkan fungsi pewarnaan pada Gn diatas maka jelas didapatkan rc(Gn ) = 4 untuk n ≥ 4. Kondisi 2. Untuk G ∼ = Bn dengan n ≥ 3. dengan jelas bahwa k(Bn ) = 3. Misalkan P = pi , p, q, pi+1 adalah rainbow path, dengan memepertimbangkan Bn terdiri atas dua buah graf bintang Sn1 dan Sn2 dengan titik pusat p dan q, serta pi dan qi adalah daun dengan masing-masing 1 ≤ i ≤ n, dan setiap titik pi adjacent ke qi . Maka rc(Bn ) ≥ 4 untuk n ≥ 3. Kemudian akan didefinisikan pewarnaan sisi pada Bn dengan c : E(G) → {1, 2, 3, 4} sesuai fungsi berikut:
ð Randhi N. Darmawan., et.al: Rainbow Connection Number
12
1, e = pq, 2, e = pp ; dengan 1 ≤ i ≤ n, i c(e) = 3, e = qqi ; dengan 1 ≤ i ≤ n, 4, e = p q ; dengan 1 ≤ i ≤ n, i i
Berdasarkan fungsi pewarnaan pada Bn diatas maka jelas didapatkan rc(Bn ) = 4 untuk n ≥ 3. 2
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 connection untuk beberapa graf khusus dan operasinya, seperti graf prisma Pn,m , graf N antiprisma APn , graf join K¯3 +Cn , dan graf tensor product of C3 Lm . 3 Teorema 1 Untuk n ≥ 3 dan m ≥ 1, rainbow connection number dari graf prisma Pn,m adalah rc(Pn,m ) =
(
m; untuk n = 3 n ⌈ 2 ⌉ + (m − 1); untuk n ≥ 4
ð Randhi N. Darmawan., et.al: Rainbow Connection Number
13
Bukti. Graf prisma adalah graf yang memiliki V (Pn,m ) = {xi,j ; 1 ≤ i ≤ n; 1 ≤ j ≤ m}, E(Pn,m ) = {xi,j xi+1,j ; 1 ≤ i ≤ n − 1; 1 ≤ j ≤ m} ∪ {xn,j x1,j ; 1 ≤ j ≤ m} ∪ {xi,j xi,j+1 ; 1 ≤ i ≤ n; 1 ≤ j ≤ m}, p = |V |=m.n dan q = |E|=2m.n − n. Berdasarkan Teorema 3 dinyatakan bahwa k(Pn,m ) ≤ rc(Pn,m ) ≤ k(Pn,m )+ 1. Untuk n = 3 graf prisma Pn,m memiliki batas atas dan bawah m ≤ rc(P3,m ) ≤ m + 1, namun dengan demikian terbukti bahwa rc(P3,m ) ≥ m. Warnai P3,m dengan fungsi f (e) = j, untuk e = xi,j xi+1,j dengan 1 ≤ i ≤ 2 dan 1 ≤ j ≤ m, e = x3,j x1,j dengan 1 ≤ j ≤ m, e = xi,j xi,j+1 dengan 1 ≤ i ≤ 3 dan 1 ≤ j ≤ m, jelas bahwa f : E(P3,m ) → {1, 2, 3, ..., m} karena rc(P3,m ) ≥ m maka rc(P3,m ) = m. Untuk n ≥ 4, graf prisma Pn,m memiliki diameter ⌈ n2 ⌉ + (m − 1) maka ⌈ n2 ⌉ + (m − 1) ≤ rc(Pn,m ) ≤ ⌈ n2 ⌉ + m, kemudian akan diwarnai dengan fungsi berikut. i + j − 1, e = xi,j xi+1,j ; dengan 1 ≤ i ≤ ⌈ n2 ⌉; 1 ≤ j ≤ m i + j − 1, e = x x dengan ⌈ n2 ⌉ + 1 ≤ i ≤ n − 1; 1 ≤ j ≤ m i,j i+1,j ; f (e) = j, e = xi,j xi,j+1 ; dengan 1 ≤ i ≤ n; 1 ≤ j ≤ m ⌊ n ⌋ + j − 1, e = x x ; dengan 1 ≤ j ≤ m − 1. n,j 1,j 2 Berdasarkan fungsi edge tersebut, warna sisi terbesar muncul pada f (e) = i + j − 1, e = xi,j xi+1,j ; dengan 1 ≤ i ≤ ⌈ n2 ⌉; 1 ≤ j ≤ m. Jika diambil nilai n dan m terbesar maka warna sisi terbesar dari Pn,m adalah ⌈ n2 ⌉ + (m − 1). Jelas bahwa f : E(Pn,m ) → {1, 2, 3, ..., ⌈ n2 ⌉ + (m − 1)} karena rc(Pn,m ) ≤ ⌈ n2 ⌉ + (m − 1). Maka, rc(Pn,m ) = ⌈ n2 ⌉ + (m − 1). 2 3 Teorema 2 Untuk n ≥ 3, rainbow connection number dari graf antiprisma APn adalah ( 2; untuk n = 3 rc(APn ) = n ⌈ 2 ⌉; untuk n ≥ 4
Bukti. Graf antiprisma APn adalah graf yang memiliki V (APn ) = {xi , yi ; 1 ≤ i ≤ n}, E(APn ) = {xi xi+1 ; 1 ≤ i ≤ n−1} ∪ {xn x1 } ∪ {yi yi+1 ; 1 ≤ i ≤ n−1} ∪ {yn y1 } ∪ {xi yi ; 1 ≤ i ≤ n} ∪ {xi yi+1 ; 1 ≤ i ≤ n−1} ∪ {x1 yn }, p = |V |=2n dan q = |E|=4n. Berdasarkan Teorema 3 dinyatakan bahwa k(APn ) ≤ rc(APn ) ≤ k(APn ) + 1. Untuk n = 3 graf AP3 mempunyai diameter 2 maka 2 ≤ rc(AP3 ) ≤ 3, namun demikian terbukti bahwa rc(AP3 ) ≥ 2. Warnai AP3 dengan fungsi berikut. ( 1, e = xi xi+1 ; 1 ≤ i ≤ 2, e = x3 x1 , e = yi yi+1 ; 1 ≤ i ≤ 2, e = y3 y1 f (e) = 2, e = xi yi , e = xi+1 yi , e = x1 y3
ð Randhi N. Darmawan., et.al: Rainbow Connection Number
14
Jelas bahwa f : E(AP3 ) → {1, 2} karena rc(AP3 ) ≤ 2. Maka, rc(AP3 ) = 2. Untuk n ≥ 4, graf APn mempunyai diameter ⌈ n2 ⌉ maka ⌈ n2 ⌉ ≤ rc(APn ) ≤ ⌈ n2 ⌉+1, kemudian akan diwarnai dengan fungsi berikut. i, e = xi xi+1 , e = xi yi ; dengan 1 ≤ i ≤ ⌈ n2 ⌉ n dengan ⌈ n2 ⌉ + 1 ≤ i ≤ n − 1 i − ⌈ 2 ⌉, e = xi xi+1 , e = xi yi ; f (e) = i, e = yi yi+1 , e = xi+1 yi ; dengan 1 ≤ i ≤ ⌈ n2 ⌉ dengan ⌈ n2 ⌉ + 1 ≤ i ≤ n − 1 i − ⌈ n2 ⌉, e = yi yi+1 e = xi+1 yi ; n − ⌈ n2 ⌉, e = xn x1 , e = yn y1 , e = x1 yn
Berdasarkan fungsi edge tersebut warna sisi terbesar muncul pada f (e) = i, e = xi xi+1 , e = xi yi dengan 1 ≤ i ≤ ⌈ n2 ⌉ dan f (e) = i, e = yi yi+1 , e = xi+1 yi . Jika diambil nilai n terbesar maka warna sisi terbesar dari APn adalah ⌈ n2 ⌉. Jelas bahwa f : E(APn ) → {1, 2, 3, ..., ⌈ n2 ⌉} karena rc(APn ) ≤ ⌈ n2 ⌉ maka rc(APn ) = ⌈ n2 ⌉. 2 3 Teorema 3 Untuk n ≥ 3, rainbow connection number dari graf join K¯3 +Cn adalah ( 2; untuk n = 3 ¯ 3 Cn ) = rc(K 3; untuk n ≥ 4
¯ 3 +Cn adalah graf yang memiliki V (K ¯ 3 +Cn ) = {xi , Yi ; 1 ≤ Bukti.Graf join K ¯ 3 +Cn ) = {x1 yi ; 1 ≤ i ≤ n} ∪ {x2 yi ; 1 ≤ i ≤ n} ∪ {x3 yi ; 1 ≤ i ≤ n} i ≤ n}, E(K ∪ {yi yi+1 ; 1 ≤ i ≤ n} ∪ {y1 yn }, p = |V |=n + 3 dan q = |E|=4n. Berdasarkan ¯ 3 +Cn ) ≤ rc(K ¯ 3 +Cn ) ≤ k(K ¯ 3 +Cn ) + 1. Teorema 3 dinyatakan bahwa k(K ¯ 3 +C3 memiliki diameter 2 maka 2 ≤ rc(K ¯ 3 +C3 ) ≤ 3 namun Untuk n = 3 graf K ¯ 3 +C3 ) ≥ 2. Warnai K ¯ 3 +C3 dengan fungsi berikut. demikian terbukti bahwa rc(K f (e) =
(
1, 2,
e = x2 yi ; i = 1, 3, e = x3 y2 , e = yi yi+1 ; 1 ≤ i ≤ 2, e = y3 y1 e = x1 yi ; 1 ≤ i ≤ 3, e = x2 y2 , e = x3 yi ; i = 1, 3
¯ 3 + C3 ) → {1, 2} karena rc(K ¯ 3 + C3 ) ≤ 2. Maka, rc(K ¯3 + Jelas bahwa f : E(K C3 ) = 2. ¯ 3 +Cn memiliki diameter 2 maka 2 ≤ rc(K ¯ 3 +Cn ) ≤ 3 namun Untuk n ≥ 4 graf K ¯ 3 + Cn ) ≥ 2, K ¯ 3 +Cn akan diwarnai dengan fungsi demikian terbukti bahwa rc(K berikut. 1, e = x1 yi ; e = x2 yi ; e = x2 yi ; e = y1 yn ; dengan i = ganjil f (e) = 2, e = x1 yi ; e = x2 yi ; e = x2 yi ; e = y1 yn ; dengan i = genap 3, e = yi yi+1 ; dengan 1 ≤ i ≤ n
ð Randhi N. Darmawan., et.al: Rainbow Connection Number
15
Berdasarkan fungsi edge tersebut warna sisi terbesar muncul pada f (e) = 3, e = yi yi+1 dengan 1 ≤ i ≤ n. Jika diambil nilai n terbesar maka warna sisi terbesar ¯ 3 + C3 adalah 3. Jelas bahwa f : E(K ¯ 3 + Cn ) → {1, 2, 3} karena rc(K ¯3 + dari K ¯ 3 + C3 ) = 3. 2 Cn ) ≤ 3. Maka, rc(K 3 Teorema 4 Rainbow connection number untuk graf tensor product C3 ⊗ Ln adalah n + 2 Bukti.Graf tensor product C3 ⊗ Ln adalah graf yang memiliki V (C3 ⊗ Ln ) = {xi,j , yi,j , zj ; 1 ≤ i ≤ 2; 1 ≤ j ≤ n}, E(C3 ⊗ Ln ) = {x1,j y1,j ; 1 ≤ j ≤ n} ∪ {x1,j x1,j+1 ; 1 ≤ j ≤ n} ∪ {y1,j y1,j+1 ; 1 ≤ j ≤ n} ∪ {x1,j x2,j ; 1 ≤ j ≤ n} ∪ {x1,j+1 x2,j ; 1 ≤ j ≤ n} ∪ {y1,j y2,j ; 1 ≤ j ≤ n} ∪ {y1,j+1 y2,j ; 1 ≤ j ≤ n} ∪ {x1,j zj ; 1 ≤ j ≤ n} ∪ {y1,j zj ; 1 ≤ j ≤ n}, p = |V | = 5n + 3 dan q = |E| = 9n + 3. Berdasarkan Teorema 3 dinyatakan bahwa k(C3 ⊗ Ln ) ≤ rc(C3 ⊗ Ln ) ≤ k(C3 ⊗ Ln ) + 1, diamater dari graf C3 ⊗ Ln = n + 2 maka n + 2 ≤ rc(C3 ⊗ Ln ) ≤ n + 3 namun demikian terbukti bahwa rc(C3 ⊗Ln ) ≥ n+2. Graf C3 ⊗Ln akan diwarnai dengan fungsi berikut. 1, e = x1,j+1 x2,j ; e = y1,j+1 y2,j ; e = x1,1 z1 ; e = y1,1 z1 ; 1 ≤ j ≤ n j, e = x y ; 1 ≤ j ≤ n 1,j 1,j f (e) = j + 1, e = x1,j x1,j+1 ; e = y1,j y1,j+1 ; e = y1,j y2,j ; e = y1,j zj ; e = y1,j zj ; 1 ≤ j ≤ n j + 2, e = x x ; 1 ≤ j ≤ n 1,j 2,j Jelas bahwa f : E(C3 ⊗ Ln ) → {1, 2, 3, ..., n + 2} karena rc(C3 ⊗ Ln ) ≤ n + 2, maka rc(C3 ⊗ Ln ) = n + 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 prisma Pn,m dengan n ≥ 3,m ≥ 1, didapatkan rainbow connection number adalah ( m; untuk n = 3 rc(Pn,m ) = n ⌈ 2 ⌉ + (m − 1); untuk n ≥ 4.
ð Randhi N. Darmawan., et.al: Rainbow Connection Number
16
Untuk graf antiprisma APn dengan n ≥ 3, didapatkan rainbow connection number adalah ( 2; untuk n = 3 rc(APn ) = n ⌈ 2 ⌉; untuk n ≥ 4
¯ 3 +Cn dengan n ≥ 3, didapatkan rainbow connection Untuk graf join K number adalah ( 2; untuk n = 3 ¯ 3 + Cn ) = rc(K 3; untuk n ≥ 4. Untuk graf tensor product C3 ⊗ Ln , didapatkan rainbow connection number adalah rc(C3 ⊗ Ln ) adalah n + 2.
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] Gary 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.
ð Randhi N. Darmawan., et.al: Rainbow Connection Number
17
[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