BILANGAN DOMINASI EKSENTRIK TERHUBUNG pada GRAF Tito Sumarsono1, R. Heri Soelistyo2, Y.D. Sumanto3 Departemen Matematika FSM Universitas Diponegoro Jl. Prof. H. Soedarto, S. H. Tembalang Semarang
[email protected]
ABSTRACT. Given a graph πΊ = (π, πΈ), comprising a set π of vertices and a set πΈ of edges. A set π· β π (πΊ) is a dominating set of πΊ, if every vertex in π β π· is adjacent to at least one vertex in π·. The cardinality of minimum dominating set of πΊ itβs domination number and is denoted by πΎ(πΊ). A set π· β π (πΊ) is a eccentric dominating set if π· is an dominating set of πΊ and for every π£ in π β π· there exist at least one eccentric point of π£ in π·. The cardinality of minimum eccentric dominating set of πΊ itβs eccentric domination number and is denoted by πΎππ (πΊ). A set π· β π (πΊ) is a connected eccentric dominating set if π· is an eccentric dominating set of πΊ and the induced subgraph < π· > is connected. The cardinality of minimum connected eccentric dominating set of πΊ itβs connected eccentric domination number and is denoted by πΎππ (πΊ). In this paper we discuss connected eccentric dominating set and connected eccentric domination number on special graphs which are complete graph, star graph, complete bipartite graph, cycel graph and wheel graph.
Keywords : eccentric dominating set, eccentric domination number, connected connected eccentric domination number
I.
eccentric dominating set,
PENDAHULUAN
Teori graf pertama kali diperkenalkan oleh Leonhard Euler seorang matematikawan berkebangsaan Swiss pada tahun 1736 ketika menyelesaikan kasus Jembatan Konigsberg. Masalah Jembatan Konigsberg adalah mungkin tidaknya melewati ketujuh jembatan yang ada di kota Konigsberg masing-masing tepat satu kali dan kembali lagi di tempat semula. Publikasi atas permasalahan ini dan solusi yang dia tawarkan saat ini dikenal dengan teori graf. Teori dan aplikasi graf mengalami perkembangan dari tahun ke tahun. Salah satu topik dalam teori graf yang masih dapat dikembangkan secara luas adalah bilangan dominasi. Pada beberapa skripsi sebelumnya telah dibahas mengenai bilangan dominasi, diantaranya βBilangan Dominasi dan Bilangan Kebebasan Graf Bipartit Kubikβ oleh Budi Santoso pada tahun 2012 [1], βPenentuan Bilangan Dominasi Complementary Tree Terhubung-3 pada Grafβ oleh Efni Agustiarini pada tahun 2015 [2] dan βPenjumlahan Bilangan Dominasi Ganda dan Konektivitas Pada Grafβ oleh Ruth Anita Hosiana Simamora pada tahun 2015 [3].
Pada tugas akhir ini dibahas himpunan dan bilangan dominasi eksentrik terhubung pada graf lengkap, graf star, graf bipartit lengkap, graf cycle dan graf wheel.
II.
2.1
HASIL DAN PEMBAHASAN
Himpunan Dominasi Eksentrik terhubung
Definisi 3.1.1 [7] Suatu himpunan π· β π(πΊ) disebut himpunan dominasi eksentrik jika π· adalah himpunan dominasi dari πΊ dan juga untuk setiap titik π£ di π β π· terdapat setidaknya satu titik eksentrik dari π£ di π·. Kardinalitas minimum dari setiap himpunan dominasi eksentrik disebut bilangan dominasi eksentrik dari πΊ dan dinotasikan sebagai πΎππ (πΊ). Definisi 3.1.2 [7] Suatu himpunan π· β π(πΊ) disebut himpunan dominasi eksentrik terhubung jika π· adalah himpunan dominasi eksentrik dari πΊ dan juga induced subgraf < π· > terhubung. Kardinalitas dari setiap himpunan dominasi eksentrik terhubung minimum disebut bilangan dominasi eksentrik terhubung dari πΊ dan dinotasikan sebagai πΎππ (πΊ).
2.2
Bilangan Dominasi Eksentrik Terhubung pada Graf Khusus
Teorema 3.2.1 [7] Bilangan dominasi eksentrik terhubung graf lengkap πΎπ adalah πΎππ (πΎπ ) = 1. Bukti: Diambil sebarang π’ β π(πΎπ ). Karena πΎπ adalah graf lengkap maka untuk setiapπ£ β π(πΎπ ) β {π’} adjacent dengan π’ sehingga {π’} merupakan himpunan dominasi dari πΎπ . Karena setiap titik di πΎπ mempunyai eksentrisitas 1 maka titik π’ juga merupakan titik eksentrik dari setiap titik di π(πΎπ ) β {π’} sehingga untuk setiap π£ β π(πΎπ ) β {π’}, π’ β πΈ(π£). Jadi π· = {π’} merupakan himpunan dominasi eksentrik terhubung. Oleh karena itu bilangan dominasi eksentrik terhubung graf lengkap πΎππ (πΎπ ) = 1. Teorema 3.2.2 [7] Bilangan dominasi eksentrik terhubung graf star πΎ1,π adalah πΎππ (πΎ1,π ) = 2 jika π β₯ 2.
Bukti: Diberikan graf star πΎ1,π , π β₯ 2 dengan himpunan titik π(πΎ1,π ) = {π£1 , π£2 , β¦ , π£π } dan himpunan sisi πΈ(πΎ1,π ) = {π£1 π£2 , π£1 π£3 , π£1 π£4 , β¦ , π£1 π£π . Diambil sebarang π’ β π(πΎ1,π ) β {π£}. Misal π = {π’, π£}, dimana π’ titik sebarang dan π£ titik pusat graf star πΎ1,π dan setiap titik di πΎ1,π selain titik pusat π£ mempunyai eksentrisitas 2 dan π’ merupakan titik eksentrik dari setiap titik π€ β πΎ1,π β π. Karena titik π’ dan π£ terhubung maka π merupakan himpunan dominasi eksentrik terhubung. Oleh karena itu πΎππ (πΎ1,π ) = 2 jika π β₯ 2.
Teorema 3.2.3 [7] Bilangan dominasi eksentrik terhubung graf bipartit lengkap (πΎπ,π ) adalah πΎππ (πΎπ,π ) = 1, jika π = 1 dan π = 1. πΎππ (πΎπ,π ) = 2, jika π β₯ 1 dan π β₯ 2. Bukti: Misal π(πΎπ,π ) dipartisi menjadi 2 himpunan titik, yaitu π1 = {π’1 , π’2 , π’3 , β¦ , π’π } dan π2 = {π£1 , π£2 , π£3 , β¦ , π£π } dengan himpunan sisi πΈ(πΎπ,π ) = {π’1 π£1 , π’1 π£2 , π’1 π£3 , β¦ , π£π ; π’2 π£1 , π’2 π£2 , π’2 π£3 , β¦ , π’2 π£π ; π’π π£1 , π’π π£2 , π’π π£3 , β¦ , π’π π£π }. Kasus I: Jika π = 1 dan π = 1 maka πΎ1,1 = πΎ2 . Dengan menggunakan Teorema 3.3.2 diperoleh πΎππ (πΎπ,π ) = 1.
Kasus II: Jika π β₯ 1, π β₯ 2. Setiap titik di π1 adjacent dengan π titik di π2 dan setiap titik di π2 adjacent dengan m titik di π1. Ambil sebarang π’, π£ β π· β π(πΎπ,π ) dimana π’ β π1 dan π£ β π2 . Karena πΎπ,π adalah graf bipartit lengkap, maka induced subgraph < π· > terhubung. Akan ditunjukkan bahwa π· = {π’, π£} merupakan himpunan dominasi eksentrik. Karena πΎπ,π adalah graf bipartit lengkap, maka π’ adjacent dengan setiap titik di π2 dan juga merupakan titik eksentrik dari semua titik π1 β {π’} demikian juga π£ adjacent dengan setiap titik di π1 dan juga merupakan titik eksentrik dari semua titik di π2 β {π£}, sehingga π· = {π’, π£} merupakan himpunan dominasi eksentrik terhubung. Oleh karena itu, πΎππ (πΎπ,π ) = 2, jika π β₯ 1, π β₯ 2.
Teorema 3.2.4 [7] Bilangan dominasi eksentrik terhubung graf cycle πΆπ adalah πΎππ (πΆπ ) = π β 2 jika π β₯ 3. Bukti: Diberikan
graf
cycle
πΆπ
dengan
π(πΆπ ) = {π£1 , π£2 , π£3 , β¦ , π£π }
dan
πΈ(πΆπ ) =
{π£1 π£2 , π£2 π£3 , β¦ , π£πβ1 π£π , π£π π£1 }. Ambil sebarang π£π β π(πΆπ ) tulis π·1 = {π£π }, karena πΆπ adalah graf cycle , maka π£π adjacent dengan π£πβ1 dan π£π+1 , tetapi π£π tidak adjacent dengan π£π+2. Sehingga π·1 = {π£π } bukan merupakan himpunan dominasi eksentrik. Oleh karena itu bentuk himpunan baru π·2 = {π£π , π£π+1 } dimana π£π adjacent dengan π£πβ1 dan π£π+1 adjacent dengan π£π dan π£π+2, tetapi π£π+1 tidak adjacent dengan π£π+3 . Sehingga π·2 = {π£π , π£π+1 } bukan merupakan himpunan
dominasi
eksentrik.
Proses
ini
berulang
sampai
diperoleh
π·πβ2 =
{π£π , π£π+1 , β¦ , π£π , π£1 , β¦ , π£πβ3 } dimana π£π adjacent dengan π£πβ1 dan π£π+1 dan π£πβ3 adjacent dengan π£πβ2 . Sehingga π·πβ2 = {π£π , π£π+1 , β¦ , π£π , π£1 , β¦ , π£πβ3 } merupakan himpunan dominasi eksentrik dari graf cycle πΆπ . Oleh karena itu πΎππ (πΆπ ) = π β 2 jika π β₯ 3. Kasus I : π genap Karena πΆπ adalah graf cycle maka eksentrisitas setiap titik di πΆπ sama dengan radius(π) di πΆπ , π
yaitu 2. Titik eksentrik dari π£π adalah π£π+π πππ(π) untuk setiap π = 1,2,3, β¦ , π. Kasus II : π ganjil Karena πΆπ adalah graf cycle maka eksentrisitas setiap titik di πΆπ sama dengan radius(π) di πΆπ , 1
yaitu 2 (π β 1). Titik eksentrik π£π adalah π£π+π πππ(π) dan π£π+(πβπ) πππ(π) untuk setiap π = 1,2,3, β¦ , π.
Teorema 3.2.5 [7] Bilangan dominasi eksentrik terhubung graf wheel ππ adalah πΎππ (ππ ) = 1, jika π = 3. πΎππ (ππ ) = 2, jika π = 4. πΎππ (ππ ) = 3, jika π β₯ 5. Bukti: Kasus I: π = π Graf wheel π3 = πΎ4 . Dengan menggunakan Teorema 3.3.2 akan diperoleh πΎππ (π3 ) = 1.
Kasus II: π = π Misal π = {π’, π£}, dimana π’ dan π£ titik sebarang dalam graf wheel π4 . Titik π’ dan π£ adjacent dan bukan merupakan titik pusat. Setiap titik di ππ selain titik pusat mempunyai eksentrisitas 2, π’ dan π£ merupakan titik eksentrik dari setiap titik π€ β πΎ1,π β π. Karena titik π’ dan π£ terhubung maka π merupakan himpunan dominasi eksentrik terhubung terhubung minimum. Oleh karena itu πΎππ (π4 ) = 2. Kasus III: π β₯ π Misal π = {π’, π£, π€} dimana π£ titik pusat dan π’, π€ dua titik sebarang yang adjacent. dengan titik π₯ β ππ β π. Setiap titik di ππ mempunyai eksentrisitas 2, π’ dan π€ merupakan titik eksentrik dari setiap titik π₯ β ππ β π. Karena titik π’, π£ dan π€ terhubung maka π merupakan himpunan dominasi eksentrik terhubung minimum. Oleh karena itu, πΎππ (ππ ) = 3.
III.
KESIMPULAN
Berdasarkan hasil pembahasan mengenai himpunan serta bilangan dominasi eksentris terhubung pada graf dapat diambil kesimpulan bahwa : 1. Untuk graf lengkap πΎπ maka πΎππ (πΎπ ) = 1. 2. Untuk graf star πΎ1,π dengan order π β₯ 2, maka πΎππ (πΎ1,π ) = 2. 3. Untuk graf bipartit lengkap πΎπ,π jika order π = π = 1, maka πΎππ (πΎπ,π ) = 1 dan jika order π β₯ 1, π β₯ 2 maka πΎππ (πΎπ,π ) = 2. 4. Untuk graf cycle πΆπ dengan order π β₯ 3, maka πΎππ (πΆπ ) = π β 2. 5. Untuk graf wheel ππ jika order π = 3, maka πΎππ (ππ ) = 1; jika order π = 4, maka πΎππ (ππ ) = 2; dan jika order π β₯ 5, maka πΎππ (ππ ) = 3.
IV. [1]
DAFTAR PUSTAKA
Santoso, Budi. 2012. Bilangan Dominasi dan Bilangan Kebebasan Graf
Bipartit
Kubik. Skripsi. Jurusan Matematika FSM. Universitas Diponegoro. Semarang. [2]
Agustiarini , Efni.2015. Penentuan Bilangan Dominasi Complementary
Tree Terhubung-3 pada Graf. Skripsi. Jurusan Matematika FSM. Universitas Diponegoro. Semarang. [3]
Simamora , Ruth Anita Hosiana. 2015. Penjumlahan Bilangan Dominasi Ganda dan Konektivitas Pada Graf . Skripsi. Jurusan Matematika FSM. Universitas Diponegoro. Semarang.
[4]
Harary, Frank. 1969. GRAPH THEORY. New York: Addison-Wesley Publishing Company.
[5]
Kamath, S.S., R.S.Bhat & Surekha R.Bhat. 2012. Strong (weak) Edge Vertex Mixed Domination Number of a Graph. Int.J. Mathematical sciences. Vol 11, no 3-4, 433444.
[6]
Wilson, j.Robin and John J.Watkins. 1990. βGraphs An Inroductory Approachβ. New York: University Course Graphs, Network, and Design.
[7]
R. Jahir Hussain, A. Fathima Begam. 2015. Connected Eccentric Domination Number in Graphs. International Journal of Innovative Trends in Engineering (IJITE). Vol 04, No 01.
