BILANGAN DOMINASI PERSEKITARAN PADA GRAF LENGKAP DAN GRAF BIPARTIT LENGKAP Lucia Ratnasari1, Bayu Surarso2, Harjito3, Uun Maunah4 1,2,3 Departemen Matematika FSM Universitas Diponegoro 4 Program Studi S1 Departemen Matematika FSM Universitas Diponegoro Jl. Prof. H. Soedarto, S.H. Tembalang Semarang Abstract. Given graph with set of vertex and set of edge E. Set subset of is called domination set if every point in − is adjacent with at least one point in in graph . The minimum cardinality of all set of domination graph is called domination number. Let be a subset of , set is called a neighborhood set if = ⋃ ∈ 〈 ( )〉 with 〈 ( )〉 induced subgraph of ( ). The minimum cardinality of all the neighborhood set of graph is called the neighborhood number. There are several types of neighborhood domination number depending on the parameters. In this paper we examine the transversal neighborhood domination number and global neighborhood domination number in complete graph and complete bipartite graph. Keywords: neighborhood domination number, transversal neighborhood domination number, global neighborhood domination number global. 1. PENDAHULUAN Salah satu topik dari teori graf adalah himpunan dominasi. Secara historis, masalah dominasi mulai dipelajari dari tahun 1950 oleh Hedetniemi dan Laskar, kemudian Haynes dkk menuliskan dalam bukunya lebih dari 75 jenis dominasi dan topik-topik lanjutan dalam dominasi yang telah didefinisikan dan diselidiki oleh beberapa penulis [1]. Himpunan dominasi dari sebuah graf = ( , ) merupakan himpunan subset dari dimana setiap titik di − bertetangga setidaknya dengan satu titik di , sedangkan bilangan dominasi adalah kardinalitas minimum dari semua himpunan dominasi dari suatu graf . Berbagai jenis parameter dari dominasi telah didefinisikan dan dipelajari oleh beberapa penulis. Untuk suatu himpunan dominasi S dari graf G juga ingin diketahui bagaimana perilaku dari himpunan persekitaran S. Beberapa kajian dengan parameter dominasi persekitaran diantaranya adalah dominasi persekitaran total, dominasi persekitaran terhubung, dominasi persekitaran terhubung equitable, dominasi persekitaran global dan dominasi 20
persekitaran transversal. Pada tulisan ini dikaji bilangan dominasi persekitaran transversal dan bilangan dominasi persekitaran global pada graf lengkap dan graf bipartit lengkap dan selanjutnya dibandingkan bilangan dominasi dengan parameter-parameter tersebut. Istilahistilah dan notasi yang tidak didefinisikan dalam tulisan ini diambil dari referensi [2] dan [3]. 2. HASIL DAN PEMBAHASAN 2.1 Bilangan Dominasi Persekitaran Transversal Sebelum membahas bilangan dominasi persekitaran transversal terlebih dahulu dijelaskan pengertian himpunan persekitaran dan himpunan persekitaran minimum. Definisi 2.1 [4] Himpunan ⊆ pada graf = ( , ) disebut himpunan persekitaran jika = ⋃ ∈ 〈 ( )〉, dengan 〈 ( )〉 subgraf induksi dari ( ). Himpunan persekitaran disebut himpunan persekitaran minimum jika himpunan tersebut mempunyai kardinalitas minimum dari semua himpunan persekitaran pada graf . Kardinalitas
Jurnal Matematika Vol. 20, No. 1, April 2017 : 20 - 26
minimum dari semua himpunan persekitaran disebut bilangan persekitaran dari dan dinotasikan sebagai ( ). Contoh 2.2 Diberikan Graf himpunan titik = , , , =
,
,
Misal diambil
Gambar 2.1 Graf ,
=
,
,
,
dengan dan , . ,
dengan himpunan
=
dinotasikan dengan ( ). Suatu himpunan dominasi persekitaran transversal dari dengan | | = ( ) disebut himpunan . Contoh 2.4 Diberikan gambar graf seperti berikut :
Gambar 2.3 Graf = ,
,
dengan himpunan dominasi
Oleh karena tidak ada himpunan persekitaran yang mempunyai kardinalitas kurang dari 2 maka kardinalitas minimum dari setiap himpunan persekitaran di graf adalah dua sehingga bilangan persekitaran dari graf adalah dua atau ( ) = 2.
Jika = ( , , ) adalah graf bipartit lengkap maka hanya terdapat satu , himpunan persekitaran minimum pada graf bipartit lengkap tersebut yaitu , = , . Misal akan dibentuk himpunan dominasi = , dengan dua titik dimana satu titiknya diambil dari = , dan satu titik lainnya diambil dari = , , maka ∩ = , ∩ , = . Karena himpunan dominasi dan himpunan persekitaran minimum beririsan maka himpunan dominasi merupakan himpunan dominasi persekitaran transversal. Oleh karena himpunan dominasi persekitaran transversal merupakan kardinalitas minimum dari himpunan dominasi persekitaran transversal yang berada pada graf bipartit lengkap , maka terbukti jika bilangan dominasi persekitaran transversal graf adalah 2.
Definisi 2.3 [4] Himpunan dominasi ⊆ dari sebuah graf disebut himpunan dominasi persekitaran transversal jika himpunan tersebut beririsan dengan setiap himpunan persekitaran minimum. Kardinalitas minimum dari himpunan dominasi persekitaran transversal disebut bilangan dominasi persekitaran transversal dan
Teorema 2.5 [4] Untuk setiap graf bipartit lengkap , berlaku ; 2, ≠ 1; ( )= 1, = 1. Bukti : Misal = ( , , ) adalah sebuah graf bipartit lengkap , maka terdapat tiga kasus yaitu : Kasus I : < atau , ≠ 1
Pada Gambar 2.1 terlihat bahwa = , merupakan himpunan persekitaran dari karena = ⋃ ∈ 〈 ( )〉 = 〈 ( )〉 ∪ 〈 ( )〉.
(a) Gambar 2.2 Subgraf Induksi dan (b) ( )
(b) dari (a)
( )
21
Lucia Ratnasari, Bayu Surarso dan Harjito (Bilangan Dominasi Persekitaran pada Graf Lengkap dan...)
Diketahui graf adalah graf bipartit lengkap untuk < atau , ≠ 1 , dengan | | = dan | | = . Karena < maka merupakan himpunan persekitaran minimum dari graf bipartit lengkap , . Kemudian setiap himpunan dominasi dengan dua titik dimana satu titik berasal dari dan satu titik lainnya berasal dari akan mendominasi semua titik pada graf bipartit lengkap , dan juga beririsan dengan sebagai himpunan persekitaran minimum pada graf bipartit lengkap , . Oleh karena himpunan dominasi beririsan dengan setiap himpunan persekitaran minimum pada graf ( ) = 2. bipartit lengkap , maka Kasus II : = Diketahui graf adalah bipartit lengkap = dimana | | = dan , untuk | | = . Karena = maka terdapat dua himpunan persekitaran minimum pada graf bipartit lengkap dan . , yaitu Kemudian setiap himpunan dominasi dengan dua titik dimana satu titik berasal dari m dan satu titik lainnya berasal dari atau sebaliknya akan mendominasi semua titik pada graf bipartit lengkap , dan juga beririsan dengan setiap himpunan persekitaran minimum pada graf bipartit lengkap , . Oleh karena himpunan dominasi beririsan dengan setiap himpunan persekitaran minimum pada graf ( ) = 2. bipartit lengkap , maka Kasus III : atau = 1 Diketahui graf adalah graf bipartit | |= lengkap dimana dan , | | = . Karena atau = 1 maka terdapat satu himpunan persekitaran minimum graf bipartit lengkap , yaitu atau = 1 yang mempunyai anggota himpunan titik berjumlah satu. Kemudian titik tersebut juga yang akan menjadi himpunan dominasi dan juga beririsan dengan himpunan persekitaran minimum pada graf bipartit lengkap , . Oleh karena himpunan dominasi beririsan dengan setiap himpunan persekitaran 22
minimum pada graf bipartit lengkap maka ( ) = 1. ∎
,
Contoh 2.6 Kasus I : Diberikan gambar graf bipartit lengkap seperti berikut :
Gambar 2.4 Graf bipartit lengkap himpunan dominasi = ,
,
dengan
Pada Gambar 2.4 merupakan graf bipartit lengkap , dengan = , , dan = , , , . Karena | | < | | maka = , , merupakan himpunan persekitaran pada graf bipartit = , . Misal himpunan dominasi , maka ∩ = , ∩ , , = . Karena himpunan dominasi beririsan dengan himpunan persekitaran maka Himpunan dominasi merupakan himpunan dominasi persekitaran transversal. Oleh karena himpunan dominasi persekitaran transversal merupakan kardinalitas minimum dari himpunan dominasi persekitaran transversal yang berada pada graf bipartit lengkap , maka terbukti jika ( , ) = 2. Kasus II : Diberikan gambar graf bipartit lengkap seperti berikut :
Gambar 2.5 Graf bipartit lengkap himpunan dominasi = ,
,
dengan
Jurnal Matematika Vol. 20, No. 1, April 2017 : 20 - 26
Pada Gambar 2.5 merupakan graf bipartit lengkap , dengan = , , dan = , , . Karena | | = | | maka terdapat dua himpunan persekitaran minimum pada graf bipartit lengkap = , , dan = , yaitu , , . Misal himpunan dominasi = , maka ∩ = , ∩ , , = dan ∩ = , ∩ , , = . Karena himpunan dominasi beririsan dengan setiap himpunan persekitaran minimum pada graf bipartit lengkap maka , Himpunan dominasi merupakan himpunan dominasi persekitaran transversal. Oleh karena himpunan dominasi persekitaran transversal merupakan kardinalitas minimum dari himpunan dominasi persekitaran transversal yang berada pada graf bipartit lengkap maka terbukti jika , = 2. , Kasus III : Diberikan gambar graf bipartit seperti berikut :
Gambar 2.6 Graf bipartit lengkap himpunan dominasi =
,
maka himpunan dominasi merupakan himpunan dominasi persekitaran transversal . Oleh karena itu himpunan dominasi persekitaran transversal merupakan kardinalitas minimum dari himpunan dominasi persekitaran transversal yang berada pada graf bipartit lengkap maka terbukti jika , = 1. , Teorema 2.7 [4] Untuk setiap graf lengkap ( )= dengan order n maka Bukti : Misal adalah sebuah graf lengkap dengan order . Oleh karena setiap titik pada graf lengkap merupakan himpunan persekitaran minimum dan juga setiap titik pada graf lengkap dapat mendominasi semua titik pada graf lengkap maka himpunan dominasi persekitaran transversal-nya adalah semua titik pada ( )= graf lengkap . Jadi terbukti .∎ Contoh 2.8 Diberikan gambar graf seperti berikut :
dengan
Pada Gambar 2.6 merupakan graf bipartit lengkap dengan | | = dan , | |= , , . Karena | | < | | maka = merupakan himpunan persekitaran pada graf bipartit lengkap Karena = mendominasi , . semua titik pada graf bipartit lengkap , maka himpunan dominasi dengan kardinalitas minimum pada graf bipartit lengkap adalah = . Karena , himpunan dominasi juga merupakan himpunan persekitaran minimum pada graf bipartit lengkap yang mana , himpunan tersebut pastilah saling beririsan
Gambar 2.7 Graf K dengan himpunan dominasi D = v ,v ,v ,v ,v
Pada Gambar 2.7 terlihat graf roda dengan order 5. Karena setiap titik merupakan himpunan persekitaran minimum = , = , = , = , = maka himpunan dominasinya haruslah beririsan dengan setiap himpunan persekitaran minimum graf . Misal = , , , , maka : ∩ = , , , , ∩ = ∩ = , , , , ∩ = ∩ = , , , , ∩ = 23
Lucia Ratnasari, Bayu Surarso dan Harjito (Bilangan Dominasi Persekitaran pada Graf Lengkap dan...)
∩ = , , , , ∩ = ∩ = , , , , ∩ = Karena himpunan dominasi beririsan dengan setiap himpunan persekitaran minimum pada graf maka merupakan himpunan dominasi persekitaran transversal pada graf . Oleh karena himpunan dominasi persekitaran transversal merupakan kardinalitas minimum dari himpunan dominasi persekitaran transversal yang berada pada ( ) = 5. graf maka terbukti 2.2 Bilangan Dominasi Persekitaran Global Sebelum dibahas himpunan dominasi persekitaran global, terlebih dahulu dibahas mengenai himpunan dominasi global, himpunan dominasi terkendali, himpunan dominasi terhubung dan himpunan dominasi independen . Definisi 2.9 [5] Suatu himpunan dominasi disebut himpunan dominasi global, jika himpunan merupakan himpunan dominasi pada graf dan graf komplemen ( ). Kardinalitas minimum dari setiap himpunan dominasi gobal disebut bilangan dominasi global dari , dan dinotasikan sebagai ( ). Contoh 2.10 Diberikan graf gambar sebagai berikut :
(a) Gambar 2.8 (a) Graf
dengan
(b) dan (b) graf
Graf mempunyai ( )= , , , , dan ( )= , , , , , , , maka didapat graf dengan ( )= , , , , dan ( )= , , . Misalkan = , , maka ( )− = , , . Karena setiap 24
titik di − bertetangga dengan minimal satu titik di maka merupakan himpunan dominasi pada graf ( )− . Graf dengan = , , . Karena setiap titik di ( )− bertetangga dengan minimal satu titik di , maka merupakan himpunan dominasi pada graf . Jadi merupakan himpunan dominasi global.
Gambar 2.9 Graf Dominasi = ,
dan
dengan Himpunan
Kardinalitas minimum dari setiap himpunan dominasi global di graf adalah 2, maka ( ) = 2. Definisi 2.11 [5] Suatu himpunan dominasi disebut himpunan dominasi terkendali jika setiap titik di − bertetangga dengan titik di serta titik di − dengan ≠ . Kardinalitas minimum dari setiap himpunan dominasi terkendali disebut bilangan dominasi terkendali dari , dan dinotasikan sebagai ( ). Definisi 2.12 [6] Suatu himpunan subset dari ( ) disebut himpunan dominasi terhubung jika himpunan dominasi dan subgraph induksi < juga terhubung. Kardinalitas minimum dari setiap himpunan dominasi terhubung disebut bilangan dominasi terhubung dari , dan dinotasikan sebagai ( ). Definisi 2.13 [6] Misalkan graf terhubung. Graf persekitaran yang dinotasikan sebagai adalah graf ( ) dimana = ( ) dan ( ) = | , ∈ ( ), terdapat ∈ ( ) sehingga , ∈ ( ). Contoh 2.14 Diberikan graf gambar sebagai berikut :
dengan
Jurnal Matematika Vol. 20, No. 1, April 2017 : 20 - 26
v1
sedemikian ⋃
v2
v7
v3
v8
v6 v5 v4 Gambar 2.10 Graf
Ditentukan graf
v1
v2
v7
v8
v6
v5
v3
v4
Gambar 2.11 Graf
Pada Gambar 2.11 terlihat bahwa gambar tersebut merupakan gambar graf persekitaran , dimana , , , , , , , , ∈ ( ) sehingga , , , , , , , , , ∈ ( ). Teorema 2.15 Jika adalah graf , bipartit lengkap dengan = , ,…, dan = , ,…, , maka = ⋃ . , Bukti : merupakan graf bipartit lengkap , dengan = , ,…, dan = , ,…, . Karena , adalah graf bipartit lengkap, maka untuk setiap titik di bertetangga dengan titik di dan setiap titik di bertetangga dengan titik di . Graf persekitaran , ∈ , , setiap terdapat ∈ , sehingga = , , , maka untuk , ∈ terdapat ∈ ( , ) sedemikian , sehingga , ∈ . Jadi , setiap titik di bertetangga dengan titik di yang lain dan setiap titik di bertetangga dengan titik di yang lain,
sehingga = ⋃ .∎
,
=
Teorema 2.15 [6] Jika , adalah graf bipartit lengkap dengan = , ,…, dan = , ,…, , maka = 2 untuk 3. , Bukti : Graf , merupakan graf bipatit lengkap, maka ( , ) dapat dipartisi menjadi 2 himpunan dan himpunan dengan = , ,…, dan = , ,…, . Karena graf adalah , graf bipatit lengkap maka setiap titik di bertetangga dengan setiap titik di dan setiap titik di bertetangga dengan setiap titik di . Diambil sebarang = , dimana titik di dan titik di . Setiap titik bertetangga dengan titik dan setiap titik bertetangga dengan titik pada graf = , , , maka merupakan himpunan dominasi untuk graf =| |= , , sehingga diperoleh , 2. Pada graf persekitaran , setiap titik di selain titik bertetangga dengan titik dan setiap titik di selain titik bertetangga dengan titik , maka = , merupakan himpunan dominasi untuk graf , sehingga = , , | | = 2. Jadi = , merupakan himpunan dominasi persekitaran global pada graf = , , maka didapat , | | = 2. ∎ Contoh 2.16 Diberikan graf gambar sebagai berikut : v
u
1
1
,
v
2
v
3
u
2
u
3
dengan
Gambar 2.12 Graf K , dan K , dengan himpunan dominasi D = {v , u }
25
Lucia Ratnasari, Bayu Surarso dan Harjito (Bilangan Dominasi Persekitaran pada Graf Lengkap dan...)
Pada Gambar 2.12 terlihat bahwa = { , } merupakan himpunan dominasi pada graf = , dan , , sehingga { , } merupakan himpunan dominasi persekitaran global untuk graf , . Jadi kardinalitas minimum dari suatu himpunan dominasi persekitaran global dari graf , adalah 2, sehingga = | | = 2. , Teorema 2.17 [6] Jika adalah graf ( )= lengkap dengan titik, maka 1 3. Bukti : Graf merupakan graf lengkap, dengan titik. Karena setiap titik pada graf bertetangga ke semua titik yang lain. Diambil sebarang = untuk setiap = 1,2, … , , karena setiap titik di ( )− bertetangga dengan itu sendiri, maka merupakan himpunan dominasi untuk graf , sehingga diperoleh ( ) = 1. Graf persekitaran adalah graf itu sendiri, maka = merupakan himpunan dominasi untuk graf ( )=| |= , sehingga diperoleh 1. ∎ Contoh 2.19 Diberikan graf gambar sebagai berikut : v
v
1
4
v1
v4 Gambar 2.13 Graf dominasi = { }
v
2
v
3
dengan
v2
v3 dan
dengan himpunan
Pada Gambar 2.13 terlihat bahwa = { } merupakan himpunan dominasi pada graf dan . Jadi = { } merupakan himpunan dominasi persekitaran global untuk graf . Kardinalitas minimum dari
26
suatu himpunan dominasi persekitaran global dari graf adalah 1, sehingga ( ) = | | = 1. 3. PENUTUP Berdasarkan hasil pembahasan mengenai himpunan serta bilangan dominasi persekitaran transversal dan bilangan dominasi persekitara global pada graf lengkap dan graf bipartit lengkap dapat diambil kesimpulan bahwa : , 1. Jika G graf lengkap dengan order maka bilangan dominasi persekitaran transversal-nya sedangkan bilangan dominasi persekitaran global-nya 1 untuk 3. 2. Jika G graf bipartit lengkap , untuk , ≠ 1 dan 3 maka bilangan dominasi persekitaran transversal dan bilangan dominasi persekitara globalnya 2 4. DAFTAR PUSTAKA [1] S. Sivakumar, N. D. Soner, A. Alwardi, (2012), Connected Equitable Domination in Graphs,1: 123-130. [2] Wilson, J. R. dan J. J. Watkins, (1990), Graphs: An Introductory Approach. Canada: John Wiley & Sons, Inc. [3] F. Harary, (1969), Graph Theory, Addison-wesley, Reading Mass. [4] M.P. Sumathi, (2014), On neighbourhood Transversal Domination in Graphs, Int. J. Contemp. Math Sciences, 9(5) : 243252. [5] I.H. Naga Raja Rao, S. V. Siva Rama Raju, (2014), Global Neigborhood Domination, Proyecciones Journal of Mathematics, 33 : 25-41. [6] C. Sivagnanan, (2012), Neighborhood Connected Domination Number of Total Graphs, Gen. Math. Notes, 25(1): 27-32.
