Copyright ©2019, Jurnal THEOREMS ( The Original Research of Mathematics ) p-ISSN: 2528-102X, e-ISSN: 2541-4321, URL: http://jurnal.unma.ac.id/index.php/th

## MENGIDENTIFIKASI BILANGAN DOMINASI LOKASI PADA GRAF BINTANG KIPAS (Identify Locating-Dominating Number in Star Fan Graph)
Anuwar Kadir Abdul Gafur 1* , Ariestha Widyastuty Bustan 2
1 Program Studi Matematika,  Fakultas MIPA, Universitas Pasifik Morotai, Jl Siswa Darame, Kec Morotai Selatan, Kabupaten Pulau Morotai, Maluku Utara, 97771, Indonesia
2 Program Studi Matematika,  Fakultas MIPA, Universitas Pasifik Morotai, Jl Siswa Darame, Kec Morotai Selatan, Kabupaten Pulau Morotai, Maluku Utara, 97771, Indonesia
* E - mail : anuwarkadirabdulgafur@gmail.com

## ABSTRAK
Penelitian  ini  bertujuan  untuk  mengidentifikasi  bilangan  dominasi-lokasi  pada  graf  bintang kipas .  Bilangan  dominasi–lokasi  dari  graf merupakan  kardinalitas terkecil dari himpunan sehingga setiap dua titik dengan , . Suatu graf dengan memiliki titik dan memiliki sisi dengan orde dan disebut graf bintang kipas yang diperoleh  dengan  menempelkan  satu  salinan pada  masing-masing  titik  pendant  dari dimana adalah graf bintang dengan titik dan sisi serta adalah graf kipas dengan titik  dan sisi.  Penelitian  ini  menggunakan  metode  studi  literatur  dengan mengumpulkan  data  dan  informasi  dari  beberapa  buku  dan  jurnal.  Hasil  penelitian menunjukkan    bahwa  biilangan  dominasi-lokasi  untuk  graf  bintang  kipas dengan orde dan adalah ( )
Kata kunci: bilangan dominasi-lokasi, himpunan dominasi-lokasi, graf bintang kipas

## ABSTRACT
This study aim to identify the locating-dominating number of star fan graphs . The locating-dominating number of a graph is defined as the cardinality of minimum of such  that  for  every  distinct  vertices ,  where , . A graph where have vertices end have edges with of order end is called fan star graph obtained by attaching one copy of to every pendant vertex from . is a star graph with vertices and
edges and is a fan graph  with
vertices and edges. The literature study method
used in this study and it carried out by collecting data and information from several books and journals. The result show that the locating-dominating of
graph with orde and is ( )
Keywords : locating-dominating number, locating-dominating set, star fan graphs
Copyright ©2019, Jurnal THEOREMS ( The Original Research of Mathematics ) p-ISSN: 2528-102X, e-ISSN: 2541-4321, URL: http://jurnal.unma.ac.id/index.php/th

## 1. PENDAHULUAN
Salah  satu  kajian  yang  menarik dalam teori graf adalah konsep dimensi metrik.  Topik  ini  diperkenalkan  oleh Slater pada tahun 1975 [1]. Pada tahun 1976  Harary  dan  Malter  [2]    juga memperkenalkannya  secara  teripsah. Slater  mengunakan  istilah locating  set atau  himpunan  lokasi,  sedangkan Harary  dan  Malter  memakai  istilah resolving  set atau  himpunan  pembeda. Slater mengaitkan
permasalahan konsep  himpunan  lokasi    yang memiliki kardinalitas minimum dengan masalah  jaringan.  Masalah  tersebut tidak  lain  adalah  permasalahan  untuk menentukan banyaknya alat pendeteksi sonar  dalam  suatu  jaringan.  Alat-alat tersebut  digunakan  sebagai  acuan sehingga lokasi dari setiap posisi dalam jaringan  tersebut  dapat  diketahui.
Khuller  dkk  [3]  pada  tahun  1996 kemudian menjelaskan aplikasi permasalahan  dimensi  metrik  graf pada  bidang  sains  komputasi  dan robotika.  Chartrand  dan  Zhang  pada tahun 2003 juga memanfaatkan masalah ini untuk navigasi robotika [4]. Konsep  himpunan  pembeda  juga diaplikasikan  oleh  Chartrand  dkk.  di tahun  2000  pada  bidang  kimia  untuk mengklasifikasi  struktur  dari  molekul- molekul  kimia  [5].  Setelah  itu, pengembangan  dalam  dimensi  metrik melahirkan  beberapa  konsep  baru, salah satunya adalah konsep himpunan dominasi-lokasi.
J. Caceres dkk. mengaitkan konsep dominasi-lokasi ini dengan permasalahan penempatan alat pendeteksi  dalam  suatu  bangunan.  J. Caceres dkk. mengasumsikan
bangunan  sebagai  graf.  Kemudian  alat pendeteksi  tersebut  ditempatkan  di beberapa  titik  di  graf.  Oleh  karena  itu, diperlukan  suatu  optimasi  untuk menentukan  banyaknya  perangkat yang  dibutuhkan  sehingga  dapat mendeteksi  masalah  di  setiap  titik.
Misalkan alat pendeteksi yang dimaksud  adalah  salah  satunya  bunyi alaram  yang  menunjukkan  terjadi kerusakan  atau  kebakaran.  Setiap alaram  akan  memberikan  sinyal  ketika mendeteksi  kerusakan  atau  kebakaran yang  berdekatan  dengan  titik  alaram ditempatkan sehingga lokasi kebakaran atau kerusakan dapat ditemukan. Suatu metoda  optimasi  untuk  menyelesaikan permasalahan  tersebut  adalah  konsep himpunan dominasi-lokasi.
Semua graf adalah dalam
makalah  ini    adalah  graf  terhubung, sederhana,  tak  berarah,  dan  terbatas. Himpunan  titik dan himpunan  sisi dari Graf didefinisikan berturut-turut oleh dan . Titik dan dikatakan tetangga di jika terdapat sisi himpunan tetangga dari titik di didefinisikan sebagai {        | . Misalkan merupakan  subhimpunan  dari , disebut  sebagai himpunan  dominasi- lokasi dari jika  untuk  setiap  titik berbeda dan di selain berlaku . Bilangan  dominasi-lokasi dilambangkan dengan ,  adalah  kardinalitas terkecil dari himpunan dominasi-lokasi dari [6]. Berdasarkan hasil penelitian sebelumnya,  Ignacio  M.  Pelayo  dan  J. Caceres  dkk  [7]  berhasil  menemukan bilangan dominasi-lokasi dari beberapa graf.    Hernando  dkk  [8]  memperluas penentuan  bilangan  dominasi-lokasi dengan menentukan
bilangan dominasi-lokasi  pada  suatu  graf dengan  komplemennya.    Oleh  karena itu,  kami  tertarik  untuk  mempelajari penentuan  bilangan  dominasi  lokasi dari  dua  buah  graf  bintang dan yang  digabungkan  disebuat  graf bintang  kipas dengan titik dan memiliki sisi dengan orde dan . Definisi 1.1.
Copyright ©2019, Jurnal THEOREMS ( The Original Research of Mathematics ) p-ISSN: 2528-102X, e-ISSN: 2541-4321, URL: http://jurnal.unma.ac.id/index.php/th
Graf  bintang dengan  orde adalah graf sederhana yang memiliki titik dan sisi yang mana setiap dua  titik di yang  berbeda bertetangga  dengan  satu  titik di tetapi titik tidak bertentangga dengan di .  Seperti  pada  Gambar  1  di bawah ini Gambar 1. Graf Bintang Definisi 1.2. Graf  kipas dengan  orde adalah  graf  sederhana  yang  memiliki titik  dan sisi  yang  mana setiap  titik di bertetangga dengan  satu  titik di dengan tetapi . Seperti pada Gambar 2 di bawah ini. Gambar 2. Graf Kipas Definisi 1.3.
Graf  bintang  kipas ( ) [9] dengan  orde adalah  graf sederhana  yang  memiliki titik  dan sisi  yang  diperoleh dengan  menempelkan  satu  titik salinan  di pada  masing-masing  titik dimana pandent  dari
serta  menggunakan  aturan  sebagai
berikut: i. ( )   { | } ii. ( )   {
| tetapi ( ) .
Gambar 3. Graf Bintang Kipas 2. METODE PENELITIAN
Metode penelitian merupakan suatu  kerangka  dalam  pemecahan masalah yang menggambarkan tahapan-tahapan  penyelesaian  masalah secara  singkat  berserta  penjelasannya. Metode  penelitian  yang  digunakan dalam  penelitian  ini  adalah  metode penelitian  studi  literature.  Tahapan- tahapan  dalam  dalam  penelitian  ini adalah  menelaah  berbagai  referensi tentang  bilangan  dominasi  lokasi, penentuan  graf  yang  akan  dicari bilangan  lokasi  dominasinya  dengan mengecek kebaruan graf yang digunakan,  dalam  hal  ini  graf  yang digunakan  adalah  graf  bintang  kipas  , jika  hasilnya  trivial  maka  akan diaplikasikan  ke  graf  lain,  jika  tidak maka  ditentukan  penentuan  bilangan dominasi  lokasi  pada  graf  bintang kipas secara umum, dan tahap terakhir adalah  pembuatan  kesimpulan  yang disajikan dalm bentuk teorema.
Copyright ©2019, Jurnal THEOREMS ( The Original Research of Mathematics ) p-ISSN: 2528-102X, e-ISSN: 2541-4321, URL: http://jurnal.unma.ac.id/index.php/th
3. HASIL DAN PEMBAHASAN
Lemma 3.1. Misalkan adalah graf  bintang  kipas  dengan  orde dan . Jika adalah  himpunan  dominasi- lokasi  dari dan  terdapat ( ) sehingga { untuk setiap ( ) selain dan maka dan Bukti. Andaikan dan . Misalkan untuk setiap ( )   { .  Karena  untuk  setiap  titik ( ) selain dan berlaku { . Maka , kontradiksi dengan himpunan  dominasi-lokasi dari . Jadi dan . Definisi 3.1. Misalkan adalah graf bintang  kipas  dengan  orde dan . Didefenisikan Gap adalah himpunan semua titik di dalam lintasan  terpendek  dari ke di selain dan . Seperti  pada
Gambar 4 di bawah ini.
Gambar 4. Gap Lemma 3.2. Misalkan adalah graf  bintang  kipas  dengan  orde dan . Jika adalah  himpunan  dominasi- lokasi  dari jika  dan  hanya jika untuk setiap memenuhi keempat sifat berikut: a. Setiap gap di memuat maksimal 3 titik; b. Misalkan adalah  gap  yang memuat  3  titik  maka untuk ; c. Misalkan adalah  gap  yang memuat  2  atau  3  titik.  Setiap yang  bertetangga  dengan harus memuat paling banyak 1 titik;
d. Paling  banyak  terdapat  satu  gap  di yang memuat 3 titik.
Bukti. Misalkan adalah himpunan dominasi- lokasi  dari .  Akan ditunjukkan  bahwa untuk memenuhi  keempat sifat tersebut. 1) Bukti sifat 1. Andaikan  terdapat  gap yang  memiliki  sedikitnya titik. Misalkan adalah himpunan dominasi-lokasi dari graf ( ) . Misalkan memuat  titik yang berada di ( ) dengan ( )   { | tetapi ( ) .  Jika tidak berada di maka ( ) dan ( ) karena ( )   { } dan ( ) { } untuk ,  kontradiksi dengan himpunan dominasi-lokasi dari .  Jadi  haruslah berada di .  Karena berada di maka
Copyright ©2019, Jurnal THEOREMS ( The Original Research of Mathematics ) p-ISSN: 2528-102X, e-ISSN: 2541-4321, URL: http://jurnal.unma.ac.id/index.php/th
( ) dan ( ) . Tetapi ( ) { ( ) ,  kontradiksi dengan himpunan dominasi-lokasi dari . Jadi, setiap gap memiliki maksimal tiga titik. 2) Bukti sifat 2. Misalkan adalah  gap  yang memuat 3 titik di , ( )   { | tetapi ( ) .  Andaikan  titik maka ( ) karena ( ) { } , ( ) { } , dan ( ) { } , kontradiksi dengan himpunan dominasi-lokasi dari . Jadi, haruslah untuk . 3) Bukti sifat 3. Misalkan  gap memuat sedikitnya dua titik. Andaikan  setiap  gap  yang bertetangga  dengan harus memuat  paling  sedikit  dua titik. tanpa mengurangi keumuman,  misalkan dan berada gap dan dan berada  di gap untuk dan dimana dan bertetangga. Misalkan  titik adalah  ujung  dari  kedua  gap dan .  Perhatikan  bahwa untuk  setiap bertetangga dengan untuk  setiap
dan ( )   { | tetapi ( ) maka ( ) { }   ( ) { } , ( ) { } dan ( ) { } . Akibatnya ( ) ( ) ,  kontradiksi. Jadi, setiap gap yang bertetangga  dengan harus memuat  paling  banyak  satu titik. 4) Bukti sifat 4. Andaikan  terdapat  dua  gap yang memuat titik. Misalkan dan adalah dua gap dengan { } dan { } untuk dan . Berdasarkan definisi 1.3 bagian (ii), maka ( ) { }   ( ) { }   ( ) { } dan ( ) { }   ( ) { }   ( ) { } . Akibatnya ( ) { ( ) dengan ,  kontradiksi  dengan himpunan dominasi-lokasi dari . Jadi, setiap gap di memuat maksimal 3 titik.
Copyright ©2019, Jurnal THEOREMS ( The Original Research of Mathematics ) p-ISSN: 2528-102X, e-ISSN: 2541-4321, URL: http://jurnal.unma.ac.id/index.php/th
Misalkan memenuhi keempat sifat tersebut. Akan ditunjukkan  bahwa himpunan dominasi-lokasi  dari . Ambil sebarang titik yang  berada di  suatu  gap.  Maka  terdapat  tiga kemungkinan  posisi yang  berada di dalam gap yang dihasilkan oleh yakni: 1) berada  di  dalam  gap yang berukuran satu; Misalkan dan di merupakan titik ujung dari gap  yang  memuat  titik . Maka saling bertetangga  tetapi tidak saling bertetangga sehingga { } karena bertetangga  dengan untuk  setiap dan . Ambil sebarang di ( ) { . Karena  titik bertetangga dengan atau , maka atau . Jadi, untuk setiap di ( ) dan berlaku . 2) berada  di  dalam  gap  yang berukuran dua; Misalkan ( ) dan hanya dengan ( ) { | tetapi ( ) , maka atau .  Tanpa mengurangi keumuman, misalkan . Kita peroleh { } sehingga { } .  Ambil  sebarang di ( ) { .
Perhatikan  bahwa  terdapat dua kemungkinan posisi . a) berada  di  dalam  gap dengan  titik  ujung . Misalkan adalah titik  ujung  gap  yang memuat .  Perhatikan bahwa tetapi . b) berada  di  dalam  gap dengan  titik  ujung  bukan .  Misalkan adalah  titik  ujung  yang memuat .  Perhatikan bahwa tetapi . Jadi,  untuk  setiap  setiap di ( ) dan berlaku . 3) berada  di  dalam  gap  yang berukuran tiga; Misalkan ( ) dan . Dari sini kita peroleh , atau Karena berada di dalam gap yang  berukuran  tiga  maka untuk . a) Perhatikan bahwa { .  Karena paling  banyak  satu  buah gap  yang  berukuran  tiga, maka adalah satu-satunya  titik  yang memenuhi { . b) atau
Copyright ©2019, Jurnal THEOREMS ( The Original Research of Mathematics ) p-ISSN: 2528-102X, e-ISSN: 2541-4321, URL: http://jurnal.unma.ac.id/index.php/th
Tanpa mengurangi keumuman, misalkan . Perhatikan bahwa ( ) dan untuk { } berdasarkan sifat 1,2 dan 3, titik adalah satu-satunya  titik  yang memiliki syarat ini. Jadi,  untuk  setiap di ( ) dan berlaku maka himpunan dominasi-lokasi dari . Lemma 3.3. Misalkan adalah graf  bintang  kipas  dengan  orde dan . Jika adalah  himpunan  dominasi- lokasi dari maka
| |
{
Bukti. Misalkan adalah  graf bintang  kipas  dengan  orde dan .  Misalkan untuk adalah himpunan dominasi-lokasi dari . 1) dan ; Berdasarkan  lemma  3.2,  pilih { atau {{ }   { |     }} maka | |
untuk
.  Akibatnya | | . 2) dan Berdasarkan  lemma  3.2,  pilih { atau {{ }   { |       } { |     }} maka | |
untuk .  Maka | | . 3) dan Berdasarkan  lemma  3.2,  pilih {{ }   { |         } { |       }} maka | | untuk .  Maka | | . 4) dan Berdasarkan  lemma  3.2,  pilih {{ }   { |           } { |         }} maka | | untuk .  Maka | | . Seterusnya 5) , dan . Berdasarkan  lemma  3.2,  pilih {{ } { |                  } { |                    }} maka | | untuk .  Maka | | Teorema  3.1.  Misalkan adalah graf bintang kipas dengan orde dan .  Maka ( ) . Bukti. Misalkan adalah  graf bintang  kipas  dengan  orde dan .  Misalkan adalah  m  buah  kipas  saling  lepas  dan titik { bertetangga  dengan untuk { di sehingga { ( ) .    Maka | ( )| dan | ( )| . Kasus 1. ( )
Copyright ©2019, Jurnal THEOREMS ( The Original Research of Mathematics ) p-ISSN: 2528-102X, e-ISSN: 2541-4321, URL: http://jurnal.unma.ac.id/index.php/th
Misalkan untuk adalah  himpunan  dominasi-lokasi  dari .  Berdasarkan  lemma  3.3, | | jika dan . Ini menunjukkan bahwa banyaknya  gap  di adalah selalu  ganjil.  Karena memenuhi keempat  sifat  di  Lemma  3.2,  maka banyaknya gap berisi maksimum 1 titik adalah buah gap dan banyaknya gap
berisi  lebih  dari  1  titik  adalah buah gap. Dengan demikian banyaknya titik  dalam  gap  maksimal  adalah dan . Akibatnya maksimal banyaknya titik dalam gap di untuk { adalah . Maka maksimal banyaknya titik dalam gap di adalah ,  kita  peroleh | | sehingga . Jadi, ( )   | |
.
Kasus 2. ( ) Misalkan untuk . Tanpa  mengurangi  keumuman,  pilih {{{ }   { |                  } { |                    }}} maka
memenuhi  keempat  sifat  pada  Lemma 3.2.  Akibatnya | | untuk , , dan . Perhatikan maka sehingga diperoleh | | .  Jadi, ( )   | | ( ) . Berdasarkan kasus 1 dan kasus 2, maka ( ) .
4. KESIMPULAN
Berdasarkan hasil dan pembahasan,  maka  diperoleh  suatu kesimpulan  bahwa  bilangan  dominasi- lokasi  untuk  graf  bintang  kipas dengan orde dan adalah ( )

## 5. SARAN
Pada  penelitian  ini,  kami mempelajari bilangan lokasi- dominasi untuk beberapa kelas graf bintang- .  Salah  satu  yang  telah kami  pelajari  dan  menentukan  graf bintang- yaitu  graf  bintang  kipas dengan orde dan .  Oleh  karena  itu penelitian ini juga kami memberikan  saran  untuk  penelitian selanjutnya di bidang ini. 1. Misalkan adalah graf lingkaran  bintang  [9].  Tentukan bilangan dominasi-lokasi dari 2. Misalkan adalah graf bintang- dengan bukan  graf  kipas.
Tentukan  bilangan  dominasi- lokasi dari

## 6. DAFTAR PUSTAKA
[1]   P,J,  Salter.  (1975).  Leaves  of  Trees, Congres. Number 14. Hal 549-559.
[2] Harary,  F.,  &  Melter,  R.  A.  (1976). On  the  metric  dimension  of  a graph. Ars Combin , 2 (191-195), 1.
[3] Khuller,  S.,  Raghavachari,  B.,  & Rosenfeld, A. (1996). Landmarks in graphs. Discrete Applied Mathematics , 70 (3), 217-229.
[4]    Chartrand,  G.,  &  Zhang,  P.  (2003). The  theory  and  applications  of resolvability  in  graphs. Congressus Numerantium , 47-68.
[5] G. Chartrand, L. Eroh, M. Johnson, dan  O.  R.  Ollerman,  resolvabililty
Copyright ©2019, Jurnal THEOREMS ( The Original Research of Mathematics ) p-ISSN: 2528-102X, e-ISSN: 2541-4321, URL: http://jurnal.unma.ac.id/index.php/th
in  graph  and  Metric  dimension  of graph., Discrete  Appl. 105,  (2000), 99-113.
[6] Jayagopal,  R.,  Rajan,  R.  S.,  &
Rajasingh,  I.  (2015).  Tight  Lower Bound For Locating-total Domination  Number. International Journal  of  Pure  and  Applied
Mathematics , 101 (5), 661-668
[7] Cáceres,  J.,  Hernando,  C.,  Mora, M.,  Pelayo,  I. M., &  Puertas,  M.  L.
(2013). Locating–dominating codes: Bounds and extremal cardinalities. Applied  Mathematics and Computation , 220 , 38-45.
[8] Hernando  Martín,  M.  D.  C.,  Mora Giné,  M.,  &  Pelayo  Melero,  I.  M.
(2013).  Locating  domination  in graphs and their complements.
[9] Bustan, A. W., & Salman, A. N. M. (2018).  The  Rainbow  Vertex- Connection  Number  of  Star  Fan Graphs. CAUCHY , 5 (3), 112-116.
[10]  Bustan,  A.  W.  (2016).  BILANGAN
TERHUBUNG  TITIK  PELANGI UNTUK GRAF LINGKARAN BINTANG ( 𝑺𝒎𝑪𝒏 ). Barekeng: Jurnal Ilmu  Matematika  dan  Terapan , 10 (2), 77-81.