Bilangan kontraksi sisi dominasi total pada Graf

INDONESIA:

Salah satu pembahasan dalam teori graf yang menarik untuk diteliti adalah penelitian mengenai dominasi total dan kontraksi sisi dominasi total, hal ini dikarenakan belum banyak peneliti yang meneliti mengenai hal ini. Sebuah himpunan titik S pada graf G (V,E) disebut himpunan dominasi total jika setiap titik v ϵ V ber-adjacent dengan unsur S. Bilangan total dominasi dari graf G dinotasikan dengan yt(G). Bilangan kontraksi dominasi total (ct_yt (G)) adalah minimum sisi yang harus dikontraksi untuk mengurangi jumlah dominasi total. Selanjutnya bilangan dominasi total setelah dikontraksi dinotasikan dengan y^'t (G).

Adapun langkah-langkah yang dilakukan dalam penelitian ini adalah: menentukan himpunan dominasi total, menetukan bilangan dominasi total, mengontraksi sisi dominasi total, menentukan pola bilangan dominasi total, pola bilangan kontraksi sisi dominasi total pada graf lintasan, graf kipas dan graf tangga, dan membuktikannya secara umum. Sehingga diperoleh rumus umumnya sebagai berikut :

1) Untuk graf lintasan (P_m) pola dominasi total sebelum dikontraksi adalah yt (P_m) = 1/2 m, m = 4x ; 1/2 (m + 1), m = 4x + 1 & m = 4x + 3 ; 1/2 (m + 2), m = 4x + 2, pola kontraksi sisi dominasi total adalah ct_yt (p_m) = 3, m = 4x ; 1, m = 4x + 1, m = 4x + 2 ; 2, m = 4x + 3, pola dominasi total setelah dikontraksi adalah y^'t (P_m) = 1/2 (m - 2), m = 4x ; 1/2 (m - 1), m = 4x + 1 & m = 4x + 3 ; 1/2 m, m = 4x + 2

2) Untuk graf kipas (F_m) pola dominasi total sebelum dikontraksi adalah yt (F_m) = 2, m ϵ N, pola kontraksi sisi dominasi total adalah ct_yt (F_m) = m, m ϵ N pola dominasi total setelah dikontraksi adalah y^'t (F_m) = 0 m ϵ N.

3) Untuk graf tangga (L_m) dominasi total sebelum dikontraksi adalah yt (L_m) = 2/3 m, m = 3x ; 1/3 (2m + 4), m = 3x + 1 ; 1/3 (2m + 2), m = 3x + 2, pola kontraksi sisi dominasi total adalah ct_yt (L_m) = 5, m = 3x ; 1, m = 3x + 1 ; 3, m = 3x + 2 pola dominasi total setelah dikontraksi adalah y^'t (L_m) = 1/3 (2m - 3), m = 3x ; 1/3 (2m + 1), m (3x + 1) ; 1/3 (2m - 1), m = 3x + 2

Penulis membahas bilangan kontraksi sisi dominasi total pada graf lintasan, graf kipas dan graf tangga, sehingga disarankan untuk penelitian selanjutnya dapat menerapkannya dengan bantuan komputer atau menerapkan pada graf lain.

English :

One of thediscussio in graph theory is interesting to study is the study of total domination and the total domination edge contraction is done because not many researchers are researching on this subject. A set S of vertices in a graph G (V,E) is called a total dominating set if every vertex v ϵ V is adjacent to an element of S. The total domination contraction number (ct_yt (G)) as the minimum number of edges which must be contracted in order to decrease the totaldomination number.Then total domination number after contracted denoted by y^'t (G).

The steps are performed in this study were: determine the set of total domination, determine the total domination number, determine total domination of the edge contractions, determine patterns of total domination number,patterns of numbers edge contraction of the total domination and prove it in general. Thus obtained the following general formula:

1) For the path graph (P_m) the pattern of total domination before is contracted yt (P_m) = 1/2 m, m = 4x ; 1/2 (m + 1), m = 4x + 1 & m = 4x + 3 ; 1/2 (m + 2), m = 4x + 2, the pattern of total domination edge contraction ct_yt (p_m) = 3, m = 4x ; 1, m = 4x + 1, m = 4x + 2 ; 2, m = 4x + 3, the pattern of total domination after is contracted y^'t (P_m) = 1/2 (m - 2), m = 4x ; 1/2 (m - 1), m = 4x + 1 & m = 4x + 3 ; 1/2 m, m = 4x + 2.

2) For the fan graph (F_m) the pattern of total domination before is contracted yt (F_m) = 2, m ϵ N, the pattern of total domination edge contraction ct_yt (F_m) = m, m ϵ N, the pattern of total domination after is contracted y^'t (F_m) = 0 m ϵ N.

3) For the ladder graph (L_m) the pattern of total domination before is contracted yt (L_m) = 2/3 m, m = 3x ; 1/3 (2m + 4), m = 3x + 1 ; 1/3 (2m + 2), m = 3x + 2, the pattern of total domination edge contraction ct_yt (L_m) = 5, m = 3x ; 1, m = 3x + 1 ; 3, m = 3x + 2, the pattern of total domination after is contracted y^'t (L_m) = 1/3 (2m - 3), m = 3x ; 1/3 (2m + 1), m (3x + 1) ; 1/3 (2m - 1), m = 3x + 2.

The author discusses total domination edge contraction number of path graph, fan graph and ladder graph, so it is advisable to further research can apply to computer assisted or apply to another graph.