Graf-Graf Khusus dan Bilangan Dominasinya

Graf-Graf Khusus dan Bilangan Dominasinya Agustina M1,2 , Ika Hesti A1,2 , Dafik1,3 1 CGANT - Universitas Jember 2 Jurusan Matematika FMIPA Universitas Jember, [email protected] [email protected] 3 Jurusan Matematika FKIP Universitas Jember, [email protected] Abstract Dominating set merupakan himpunan titik yang mendominasi titik-titik yang bertetangga dan seminimal mungkin. Himpunan D ⊆ V (G) adalah dominating set dari titik jika setiap titik di V (G) bertetangga dengan sebuah titik di D. Domination number γ(G) adalah kardinalitas terkecil dari sebuah dominating set. Nilai dari domination number selalu γ(G) ⊆ V (G). Penelitian ini mengembangkan dominating set pada beberapa graf khusus diantaranya adalah graf Shackel (Sm , n), graf Cn ⊙ (P4 + K 1 ), graf join Cn + Pn , graf Lobster Li,j,k , dan graf Triangular Ladder Ln . Hasil dari penelitian ini adalah beberapa teorema yang menyatakan kardinalitas minimal dominating set. Key Words : Dominating set, Domination number.

Pendahuluan Sejarah dominating set dimulai pada tahun 1850 di Eropa. Untuk menyelesaikan masalah pada papan catur 8 × 8 diperlukan minimal berapa Queen agar semua posisi dapat diserang langsung oleh Queen. Secara matematis dipelajari sejak tahun 1960 yang kemudian berkembang pada aplikasi seperti komunikasi, jaringan komputer, teori jaringan sosial, pemasangan kamera pengawas, dan penempatan pos pantau. Dominating set merupakan subset D ⊆ V dari titik di G sedemikian hingga untuk semua titik v ∈ V , salah satu dari v ∈ D atau sebuah tetangga u dari v ada di D. Domination number dinotasikan γ(G) adalah kardinalitas minimum dari sebuah dominating set. Nilai dari domination number selalu γ(G) ⊆ V (G) [6]. Penelitian terkait dominating set berkembang cukup pesat [7] [1][9][10][11]. Dalam penelitian ini mengembangkan dominating set pada beberapa graf khusus dan operasinya diantaranya adalah graf Shackel (Sm , n), graf Cn ⊙ (P4 + K 1 ), graf join Cn + Pn , graf Lobster Li,j,k , dan graf Triangular Ladder Ln .

Teorema yang Digunakan Teorema terkait batas atas dan bawah dari domination number Theorem 1 [6]Untuk sebarang graf G,

Agustina M, et.al: Graf-Graf Khusus dan Bilangan Dominasinya

544

p ⌈ 1+∆(G) ⌉ ≤ γ(G) ≤ p − ∆(G)

Bukti. Misalkan S adalah sebuah dominating set dari G. Pertama, kita andaikan batas bawah. Setiap titik dapat sebagai dominating set dan ∆(G) ke p titik yang lain. Berakibat, γ(G) ≥ ⌈ 1+∆(G) ⌉. Untuk batas atasnya, misalkan v adalah titik dengan degree maksimum ∆(G). Maka v sebagai dominating set N [v] dan titik di V − N [v] merupakan dominating set mereka sendiri. Berakibat, V − N [v] merupakan dominating set dengan kardinalitas n − ∆(G), sehingga γ(G) ≤ n − ∆(G).

Hasil Penelitian dan Pembahasan Pada bagian ini, peneliti mengembangkan dominating set yang berjarak satu pada graf khusus meliputi graf Shackel (Sm , n), graf Cn ⊙ (P4 + K 1 ), graf join Cn + Pn , graf Lobster Li,j,k , dan graf Triangular Ladder Ln . 3 Teorema 1 Misal G adalah graf Shackel(Sm , n) yang dinotasikan dengan Shackel (Sm , n) untuk n ≥ 2 dan m ≥ 3. Maka bilangan dominasinya adalah γ(Shackel(Sm , n)) = n. Bukti. Graf Shackel(Sm , n) adalah graf dengan himpunan titik V = {xi ; 1 ≤ i ≤ n} ∪ {zi ; 1 ≤ i ≤ n + 1} ∪ {xi,j ; 1 ≤ i ≤ n, 1 ≤ j ≤ m − 2} dan himpunan sisi E = {zi xi ∪ xi zi+1 ; 1 ≤ i ≤ n} ∪ {xi xi,j ; 1 ≤ i ≤ n, 1 ≤ j ≤ m} serta p = |V | = mn + n − 1, q = |E| = mn, dan ∆ = m. Pilih titik yang menjadi dominating set D = {xi ; 1 ≤ i ≤ n}, maka dengan mudah dapat dilihat bahwa D adjacent dengan semua elemen V \ D. Kardinalitas |D| = n sehingga p γ(Shackel(Sm , n)) = n. Berdasarkan teorema 1 dinyatakan bahwa ⌈ 1+∆ ⌉≤γ≤ p − ∆, untuk nilai p dan ∆ diperoleh batas atas dan bawah domination number yaitu ⌈ n(m+1)−1 ⌉ ≤ γ ≤ m(n − 1) + n − 1. Maka γ(Shackel(Sm , n)) berada dalam m+1 interval batas dominating number yaitu ⌈ n(m+1)−1 ⌉ ≤ γ ≤ m(n − 1) + n − 1. 2 m+1 3 Teorema 2 Misal G adalah graf Cn ⊙ (P4 + K 1 ), untuk n ≥ 3 memiliki domination number γ(Cn ⊙ (P4 + K 1 )) = n. Bukti. Graf Cn ⊙ (P4 + K 1 ) adalah graf dengan himpunan titik V (Cn ⊙ (P4 + K 1 )) = {xi ; 1 ≤ i ≤ n} ∪ {xi,j ; 1 ≤ i ≤ n, 1 ≤ j ≤ 5} dan himpunan sisi E(Cn ⊙ (P4 + K 1 )) = {x1 xn , xi xi+1 ; 1 ≤ i ≤ n − 1} ∪ {xi xi,j ; 1 ≤ i ≤ n, 1 ≤ j ≤ 5} ∪ {xi,j xi,j+1 , xi,1 xi,5 ; 1 ≤ i ≤ n, 1 ≤ j ≤ 5} ∪ {xi,1 xi,3 , xi,1 xi,4 ; 1 ≤ i ≤ n}

545


serta p = |V | = 6n, q = |E| = 9n, dan ∆(Cn ⊙ (P4 + K 1 )) = 5. Pilih titik yang menjadi dominating set D = {xi,1 ; 1 ≤ i ≤ n}, maka dengan mudah dapat dilihat bahwa D adjacent dengan semua elemen V \ D. Kardinalitas |D| = n sehingga p γ(P4 +K 1 ) = n. Berdasarkan teorema 1 dinyatakan bahwa ⌈ 1+∆(C ⊙(P ⌉≤ +K )) n

4

1

γ ≤ p − ∆(Cn ⊙ (P4 + K 1 )), untuk nilai p dan ∆(Cn ⊙ (P4 + K 1 )) diperoleh batas atas dan bawah domination number yaitu ⌈n⌉ ≤ γ(Cn ⊙ (P4 + K 1 )) ≤ 6n − 5. Maka γ(P4 + K 1 ) berada dalam interval batas dominating number yaitu ⌈n⌉ ≤ 2 γ(Cn ⊙ (P4 + K 1 )) ≤ 6n − 5. 3 Teorema 3 Misal G adalah graf Join Cn + Pn , untuk n ≥ 3 memiliki domination number γ(Cn + Pn ) = ⌈ n3 ⌉. Bukti. Graf Join Cn +Pn adalah graf dengan himpunan titik V (Cn +Pn ) = {xi , yi ; 1 ≤ i ≤ n3 } dan himpunan sisi E(Cn + Pn ) = {x1 yn } ∪ {xi xi+1 , 1 ≤ i ≤ n − 1} ∪ {xi yj ; 1 ≤ i ≤ n; 1 ≤ j ≤ n} ∪ {yi yi+1 ; 1 ≤ i ≤ n − 1} serta p = |V | = 2n, q = |E| = n2 + 2n − 1, dan ∆(Cn + Pn ) = n + 2. Pilih titik yang menjadi dominating set D = {x3i−2 ; 1 ≤ i ≤ ⌈ n3 ⌉}, maka dengan mudah dapat dilihat bahwa D adjacent dengan semua elemen V \ D. Kardinalitas |D| = ⌈ n3 ⌉ sehingga γ(Cn +Pn ) = ⌈ n3 ⌉. Berdasarkan teorema 1 dinyatakan bahwa ⌈ 1+∆(Cpn +Pn ) ⌉ ≤ γ(Cn + Pn ) ≤ p − ∆(Cn + Pn ), untuk nilai p dan ∆(Cn + Pn ) 2n diperoleh batas atas dan bawah domination number yaitu ⌈ n+3 ⌉ ≤ γ(Cn +Pn ) ≤ n − 2. Maka γ(Cn + Pn ) berada dalam interval batas dominating number yaitu 2n ⌈ n+3 ⌉ ≤ γ(Cn + Pn ) ≤ n − 2. 2 3 Teorema 4 Misal G adalah graf Lobster Li,j,k , untuk n ≥ 2 memiliki domination number γ(Li,j,k ) = 2n. Bukti. Graf Lobster Li,j,k adalah graf dengan himpunan titik V (Li,j,k ) = {xi ∪ xi,j ∪ xi,j,k ; 1 ≤ i ≤ n, 2 ≤ j ≤ p, 1 ≤ k ≤ l} dan himpunan sisi E(Li,j,k ) = {xi xi+1 ; 1 ≤ i ≤ n − 1} ∪ {xi xi,j ∪ xi,j xi,j,k ; 1 ≤ i ≤ n, 1 ≤ j ≤ p, 1 ≤ k ≤ l} serta p = |V | = 6n, q = |E| = 5n − 1, dan ∆(Li,j,k ) = 4. Pilih titik yang menjadi dominating set D = {xi,1 ∪ xi,2 ; 1 ≤ i ≤ n}, maka dengan mudah dapat dilihat bahwa D adjacent dengan semua elemen V \ D. Kardinalitas |D| = 2n p sehingga γ(Li,j,k ) =. Berdasarkan teorema 1 dinyatakan bahwa ⌈ 1+∆(L ⌉≤ i,j,k ) γ(Li,j,k ) ≤ p − ∆(Li,j,k ), untuk nilai p dan ∆(Li,j,k ) diperoleh batas atas dan bawah domination number yaitu ⌈ 6n 5 ⌉ ≤ γ(Li,j,k ) ≤ 6n − 3. Maka γ(Li,j,k ) berada dalam interval batas dominating number yaitu ⌈ 6n 5 ⌉ ≤ γ(Li,j,k ) ≤ 6n − 3.

Agustina M, et.al: Graf-Graf Khusus dan Bilangan Dominasinya Maka γ(Li,j,k ).

546 2

3 Teorema 5 Misal G adalah graf Triangular Ladder Ln memiliki domination number ( ⌈ n2 ⌉, untuk n = 3 dan n = 2k dimana k ≥ 2 γ(Ln ) = ⌊ n2 ⌋, untuk n = 2k + 1 dimana k ≥ 2 Bukti. Graf Triangular Ladder Ln adalah graf dengan himpunan titik V (Ln ) = {ui , vi ; 1 ≤ i ≤ n} dan himpunan sisi E(Ln ) = {ui ui+1 , vi vi+1 ; 1 ≤ i ≤ n − 1} ∪ {ui vi ; 1 ≤ i ≤ n} serta p = |V | = 2n, q = |E| = 4n − 3, dan ∆(Ln ) = 4. Pilih titik yang menjadi dominating set D = {y4i−2 ∪ x4j ; 1 ≤ i ≤ ⌈ n4 ⌉, 1 ≤ j ≤ ⌊ n4 ⌋}, untuk n = 3 dan n = 2k dimana k ≥ 2 maka dengan mudah dapat dilihat bahwa D adjacent dengan semua elemen V \ D, kardinalitas |D| = ⌈ n2 ⌉ sehingga γ(Ln ) = ⌈ n2 ⌉, untuk n = 3 dan n = 2k dimana k ≥ 2. Sedangkan untuk n yang lainnya, pilih titik yang menjadi dominating set D = {y2 , x2i+2 ; 1 ≤ i ≤ ⌊ n2 ⌋}, maka dengan mudah dapat dilihat bahwa D adjacent dengan semua elemen V \D, kardinalitas |D| = ⌊ n2 ⌋ sehingga γ(Ln ) = ⌊ n2 ⌋, untuk n = 2k + 1 dimana k ≥ 2. p Berdasarkan teorema 1 dinyatakan bahwa ⌈ 1+∆(L ⌉ ≤ γ(Ln ) ≤ p − ∆(Ln ), n) disubtitusikan nilai p dan ∆(Ln ) diperoleh batas atas dan bawah domination number yaitu ⌈ 2n 5 ⌉ ≤ γ(Ln ) ≤ 2n − 4. Maka γ(Ln ) berada dalam interval batas dominating number. 2

Kesimpulan Pada penelitian ini difokuskan pada domination number γ(G) berjarak satu pada beberapa graf khusus dan operasinya. Berdasarkan hasil penelitian diatas, maka kita dapat menyimpulkan bahwa: • Untuk graf Shackel(Sm , n) dengan n ≥ 2 dan m ≥ 3, didapatkan domination number γ (Shack (Sm , n)) = n. • Untuk graf Cn ⊙ (P4 + k 1 ) dengan n ≥ 3, didapatkan domination number γ(Cn ⊙ (P4 + k 1 )) = n. • Untuk graf Join Cn + Pn dengan n ≥ 3, didapatkan domination number γ(Cn + Pn ) = ⌈ n3 ⌉


547

• Untuk graf Lobster Li,j,k dengan n ≥ 2, didapatkan domination number γ(Li,j,k ) = 2n • Untuk graf Triangular Ladder Ln , didapatkan domination number ( ⌈ n2 ⌉, untuk n = 3 dan n = 2k dimana k ≥ 2 γ(Ln ) = ⌊ n2 ⌋, untuk n = 2k + 1 dimana k ≥ 2

References [1] A. D. Jumani, L. Chand, Dominating Number of Prism over Cycle Cn , Sindh University Research Journal (Science Series), Sindh Univ. Res. Jour. (Sci. ser) Vol.44 (2) 237-238 (2012). [2] Dafik, M. Miller, J. Ryan and M. Baˇca, Antimagic total labeling of disjoint union of complete s-partite graphs, J. Combin. Math. Combin. Comput., 65 (2008), 41–49. [3] Dafik, Structural Properties and Labeling of Graphs, University of Ballarat, 2007. [4] Goddard, W and Henning, M.A. Independent Domination in Graphs: A Survey and Recent Results. South African National Research Foundation and The University Of Johannesburg, 2006. [5] Haynes, T.W and Henning, M.A, Total Domination Good Vertices in Graphs. Australasian Journal of Combinatorics, 26 (2002), 305-315. [6] Haynes, T.W, Fundamental of Domination in Graphs, New York: Marcel Dekker, INC., 1998. [7] Hesti, I.K, Dafik, On the Domination Number of Some Families of Special Graph, Jember: University of Jember, 2014. [8] Joseph A. Gallian, A Dynamic Survey of Graph Labeling, University of Minnesota, 1997. [9] Liedloff, Dominating Set on Bipartite Graphs, Universit´e Paul VerlaineMetz, 2009. [10] Y. B. Maralabhavi, Anupama S. B., Domination Number of Jump Graph, International Mathematical Forum, Vol. 8, 2013, no. 16, 753 - 758. 2013.


548

[11] Michael A. Henning, Anders Yeo, A New Upper Bound on The Total Domination Number of a Graph, the electronic journal of combinatorics 14, 2007.

Graf-Graf Khusus dan Bilangan Dominasinya

Recommend Documents