Bilangan kontraksi sisi dominasi pada Graf

INDONESIA :

Diberikan dua titik u dan v di G, dikatakan u mendominasi v jika v ∈ N[u]. Himpunan bagian D ⊆ V(G) disebut himpunan dominasi jika titiknya mendominasi semua titik di G. Bilangan dominasi pada G dinotasikan dengan y(G) merupakan kardinal minimum dari semua himpunan dominasi. Bilangan kontraksi sisi dominasi dari sebuah graf ct_y(G) didefinisikan sebagai jumlah sisi minimal yang harus dikontraksi untuk mengurangi bilangan dominasi nya. Dalam penelitian ini, bilangan dominasi setelah kontraksi disimbolkan dengan y^'(G).

Sejauh ini, penelitian mengenai bilangan kontraksi sisi dominasi dibatasi oleh beberapa graf sederhana. Oleh karena itu penelitian ini bertujuan mengkaji lebih lanjut untuk memberikan kontribusi terhadap keilmuan di bidang matematika. Langkah-langkah penelitian adalah mencari himpunan dominasi dari beberapa graf, menentukan bilangan dominasi, kemudian mengkontraksinya, setelah itu membuat pola dan membuktikannya.

Berdasarkan hasil pembahasan, diperoleh pola sebagai berikut:
1. Pola bilangan dominasi pada graf sikel (C_n) dengan n ≥ 4 adalah
y(C_n)= {(n/3,n≡0 (mod 3)@(n+2)/3,n≡1 (mod 3) @(n+1)/3,n≡2 (mod 3))
y^'(C_n)= {((n-3)/3,n≡0 (mod 3)@(n-1)/3,n≡1 (mod 3) @(n-2)/3,n≡2 (mod 3))
Pola bilangan kontraksi sisi dominasi pada graf sikel (C_n) dengan n ≥ 4 adalah
ct_y(C_n)= {(3,n≡0 (mod 3)@ (1,n≡1 (mod 3) @(2,n≡2 (mod 3))
2. Pola bilangan dominasi pada graf roda (W_n) dengan n ≥ 4 adalah
y(W_n)= 1;y^'(W_n)=0
Pola bilangan kontraksi sisi dominasi pada graf roda (W_n) dengan n ≥ 4 adalah
ct_y(W_n) = n
3. Pola bilangan dominasi pada graf bunga (F_n) dengan n ≥ 5 adalah
y(F_n)= 1;y^'(F_n)=0
Pola bilangan kontraksi sisi dominasi pada graf bunga (F_n) dengan n ≥ 5 adalah
ct_y(F_n)=2n
Pada skripsi ini penulis membahas beberapa graf sederhana. Oleh karena itu penulis menyarankan untuk mengembangkannya pada graf-graf lain.

ENGLISH :

Given two vertices u and v in G, we say u dominates v if v ∈ N[u]. A subset D ⊆ V(G) is called a dominating set if its vertices dominate all vertices of G. The domination of G denotated by y(G) is the minimum cardinality of all dominating sets. The domination contraction number ct_y(G) as the minimum number of edges which must be contracted in order to decrease the domination number. In this research, domination number after contraction detotated by y^'(G).

Until now, the research has been done is about some simple graph domination edge contraction number. However, this research will be more discussed to give the contribution for mathematic. To find the general form we must find dominating set, find the domination number, then contracted domination number and then make a general pattern and prove it.

Based on the research, we know that:
1. The general form for domination number of cycle graph (C_n) with n ≥ 4 is
y(C_n)= {(n/3,n≡0 (mod 3)@(n+2)/3,n≡1 (mod 3) @(n+1)/3,n≡2 (mod 3))
y^'(C_n)= {((n-3)/3,n≡0 (mod 3)@(n-1)/3,n≡1 (mod 3) @(n-2)/3,n≡2 (mod 3))
The general form for domination edge contraction number of cycle graph (C_n) with n ≥ 4 is
ct_y(C_n)= {(3,n≡0 (mod 3)@ (1,n≡1 (mod 3) @(2,n≡2 (mod 3))
2. The general form for domination number of wheel graph (W_n) with n ≥ 4 is
y(W_n)= 1;y^'(W_n)=0
The general form for domination edge contraction number of wheel graph (W_n) with n ≥ 4 is
ct_y(W_n) = n
3. The general form for domination number of flower graph (F_n) with n ≥ 5 is
y(F_n)= 1;y^'(F_n)=0
The general form for domination edge contraction number of flower graph (F_n) with n ≥ 4 is
ct_y(F_n)=2n
In this research, the writer find about domination edge contraction and total domination contraction number from some simple graph. So, the writer suggest the future research can be develop it in other graph.