Jurnal Pendidikan, Matematika dan Sains http://ejournal.uki.ac.id/index.php/edumatsains

## BILANGAN DOMINASI LOKASI PADA LINE PAN GRAPH

## DAN MIDDLE PAN GRAPH
Fransiskus Fran 1* , Elishabet Yohana 2 , Yundari 3
1,2,3 Jurusan Matematika FMIPA Universtas Tanjungpura
Diterima: 18 Mei 2021     Direvisi: 19 Juni 2021     Diterbitkan : 01 Juli 2021

## ABSTRACT
One  of  the  branches  of  mathematic  that  is  useful  for  solving  problem  in  everyday  life  is  graph  theory. Graph theory  is  the  study  of graphs,  which  are  mathematical  structures  used  to  model  pairwise  relations between  objects  (nodes  and  edges).    One  of  the  topics  in  graph  theory  is  the  dominating  set  and  domination number.  Let be  a  simple,  connected,  and  undirected  graph and a  set    is a  subset  of  V.  If  every node  of adjacent at least  one node  in  ,  then  D is a  dominating  set  of  the  graph  .  One  of  the  topics from dominating set is locating dominating set. Locating dominating set is dominating set on condition if every two vertices satisfy with . The locating domination number of  graph    is  the  minimum  cardinality  of  a  locating  dominating  set  in  a  graph  .  The  locating  domination number  of  a  graph    denoted  by
.  In this  study  discussed  the  locating  domination number  on  line  pan graph and  middle  pan  graph
.  Locating  domination  number  was  obtained  by  finding dominating set from some graph. Then, does the dominating set meet the condition of locating dominating set? If it meets locating dominating set condition, then we can find the locating domination number of the graphs. In the  last  procedure,  we  get  pattern  location  domination  number  of  line  pan  graph  and  middle  pan  graph.  The results  of  the  study  obtained  the  locating  domination  number  is and
.
Keywords: Pan graph, Locating dominating set, neighbourhood of the vertex

## PENDAHULUAN
Perkembangan  teknologi  salah  satunya didukung oleh perkembangan ilmu matematika,  baik  secara  teori  maupun penerapannya  yang  mempunyai  peranan penting  dalam menyelesaikan berbagai permasalahan  yang  ada.  Salah  satu  kajian ilmu matematika yang cukup pesat perkembangannya  adalah  teori  graf,  yang diperkenalkan  pada  1736  oleh  Leonhard Euler  yang  merupakan  matematikawan
Swiss,  melalui  tulisannya  tentang  upaya pemecahan  masalah  jembatan di Sungai Pregel yang mengalir mengitari pulau Kneiphof.  Beberapa  permasalahan  lain  yang telah  dipecahkan  menggunakan  teori  graf diantaranya  adalah  jaringan  komunikasi, ilmu  komputer,  riset  operasi  dan  lain sebagainya (Munir, 2010).
Berdasarkan perkembangannya, terdapat  banyak  topik  kajian  dalam  teori graf,  salah  satunya  tentang  himpunan
dominasi.  Misal  diberikan  graf yang
merupakan pasangan himpunan , dengan menyatakan  himpunan  tidak kosong  dari  simpul-simpul  dan adalah subhimpunan dari dan disebut himpunan  sisi  (Munir,  2010).  Misalkan adalah  subhimpunan  dari .  Jika  masing- masing  simpul  dari bertetangga dengan  setidaknya  satu  simpul  dari  ,  maka disebut  himpunan  dominasi  dari
(Santoso,  Djuwandi,  &  Soelistyo,  2012). Terdapat  beberapa  pengembangan  terkait himpunan  dominasi  dengan  menambahkan syarat  tertentu,  salah  satunya  berkaitan dengan  konsep  lokasi  dan  disebut  himpunan dominasi lokasi.
Penelitian sebelumnya tentang
bilangan  dominasi  lokasi,  telah  diteliti  pada graf  lintasan,  graf cycle dan pan  graph (Yohana,  Yundari,  &  Fran,  2020).  Bilangan dominasi  lokasi  juga  pernah  diteliti  untuk graf  bipartit  dan  komplemennya  (Hernando, Mora, & Pelayo, 2018), graf interval dan graf permutasi  (Foucaud,  Mertzios,  R  Naserasr,
& Valicov, 2016), Petersen graph (Balbuena,  Foucaud,  &  Hansberg,  2015), functigraphs (Murtaza,  Fazil,  Javaid,  &
Benish, 2017) dan korona dari  beberapa graf (Canoy  &  Malacas,  2014).  Dalam  hal  ini korona graf merupakan salah satu cara untuk memperoleh  graf  baru  dari  graf-graf  yang sudah  ada.  Selain  itu,  terdapat  banyak  cara untuk  membentuk  graf  baru  dari  graf-graf
yang  sudah  ada.  Oleh  karena  itu,  penelitian terkait  bilangan  dominasi  lokasi  untuk  graf- graf  hasil  operasi  maupun  hasil  konstruksi dari  graf-graf  yang  sudah  ada  masih  sangat terbuka.  Hal  ini  diantaranya  untuk  melihat karakteristik bilangan dominasi yang dihasilkan  dari  graf  baru  tersebut.  Pada artikel ini, dibahas  bilangan dominasi lokasi pada  graf  hasil  konstruksi  dari pan  graph menggunakan  konsep line  graph dan middle graph .

## METODE PENELITIAN
Salah  satu  terminologi  dasar  graf terkait  himpunan  dominasi  lokasi  adalah persekitaran
simpul. Himpunan disebut persekitaran  terbuka  simpul di , sedangkan
menyatakan persekitaran tertutup simpul   di   (Murtaza, Fazil,  Javaid,  &  Benish,  2017) . Pada  artikel ini, dibahas tentang bilangan dominasi lokasi untuk  graf sederhana,  hingga, terhubung dan tak  berarah  yang  merupakan  graf  hasil konstruksi  dari pan  graph . Pan  graph merupakan graf yang dibentuk dari graf cycle dan  graf dengan    menghubung  salah satu titik di ke sehingga terbentuk satu sisi  penghubung  (Sddiqui  &  James,  2018). Pada  artikel  ini, pan  graph dinyatakan dengan (Ayhan  &  Omar,  2010).  Graf cycle adalah  graf  sederhana  dan  teratur dengan  masing-masing  simpulnya  memiliki derajat  dua.  Graf cycle dinotasikan
dengan menyatakan  banyaknya  simpul (Munir,  2010).  Suatu  graf    baru  dapat diperoleh  menggunakan  konsep middle graph dan line  graph .  Definisi  mengenai middle  graph diberikan  pada  Definisi  1  dan line graph pada Definisi 2.
Definisi 1 (Vaidya & Bantva, 2010)] Middle graph dari suatu graf   dilambangkan merupakan  graf  dengan  himpunan  simpul
Dua  simpul  di bertetangga  jika  dan hanya jika:
1. bertetangga dengan karena sisi dan sisi bersisian dengan simpul yang  sama  di    dengan dan dimana dengan dimana . 2. bertetangga dengan karena sisi
bersisian  dengan  simpul dengan dimana dan dimana . Definisi  2 (Roza,  Narwen,  &  Zulakmal, 2014) Misal diberikan graf . Line graph dari dilambangkan  dengan adalah  graf dengan dan  simpul-simpul
di bertetangga jika dan hanya jika sisi-
sisi  yang  bersesuaian  saling  bertetangga  di
.
Untuk  suatu  graf yang  diberikan, ilustrasi line  graph dan middle  graph dapat dilihat pada Gambar 1. Pada Gambar 1 (a)  merupakan  graf ,  Gambar  1  (b) merupakan hasil konstruksi graf menggunakan  konsep line  graph dan Gambar  1  (c)  merupakan  hasil  konstruksi graf   menggunakan konsep middle graph .
(a) (b) (c)
Gambar 1. (a) Graf G , (b) Graf ,  (c) Graf
Langkah awal dalam penelitian ini adalah
mengkonstruksi dan
menggunakan  Definisi  1  dan  Definisi  2 dengan  graf  dasarnya  yaitu .  Langkah selanjutnya, dicari himpunan dominasi masing-masing  graf  tersebut.  Kemudian memeriksa apakah syarat himpunan dominasi  lokasi  dipenuhi  oleh  himpunan dominasi  tersebut.  Jika  memenuhi  dan mempunyai  kardinalitas  minimum,  maka dapat  diperoleh  bilangan  dominasi  lokasi untuk graf dan .

## HASIL DAN PEMBAHASAN
Pada  tahun  1960,  himpunan  dominasi mulai dipelajari dalam studi  matematika dan berkembang hingga memiliki banyak aplikasi dalam kehidupan sehari-hari (Kumar,  2011).  Selain  aplikasinya,  terdapat beberapa  variasi  hasil  pengembangan  teori tentang himpunan dominasi dengan menambahkan  syarat  tertentu  misalnya himpunan dominasi lokasi. Penerapan konsep  himpunan  dominasi  lokasi  telah dikaji  oleh  Slater  pada  tahun  1980an,  yang mengaplikasikan konsep  himpunan dominasi lokasi  untuk  membuat  sebuah  kode  lokasi perlindungan  pada  beberapa  fasilitas  dengan menggunakan  jaringan  detektor  (Balbuena, Foucaud,  &  Hansberg,  2015).  Untuk  lebih jelas  terkait  himpunan  dominasi  lokasi diberikan pada Definisi 3.
Definisi  3 (Chellali,  Mimouni,  &  Slater, 2010)  Diberikan  graf dengan  himpunan simpul .  Himpunan merupakan himpunan  dominasi  lokasi  jika    himpunan dominasi  dan  untuk  setiap dengan berlaku . Bilangan dominasi  lokasi  graf
merupakan kardinalitas minimum dari himpunan dominasi lokasi graf  .
Contoh  4 Misalkan  graf di  Gambar  2, simpul  berwarna  merah  menyatakan  simpul- simpul  pada  salah  satu  himpunan  dominasi di  .
Gambar 2. Dominasi Lokasi Graf
Berdasarkan  Gambar  2  dan  Definisi  3, diperoleh  himpunan  dominasi  lokasi  graf
adalah , , dan .  Oleh karena itu diperoleh, .
Graf  utama  yang  dirujuk  pada  penelitian ini  adalah pan  graph .  Berikut  diberikan
Proposisi  5  terkait  bilangan  dominasi  lokasi graf . Proposisi  5 (Yohana,  Yundari,  &  Fran, 2020)  Diberikan  pan  graph
.  Bilangan
dominasi lokasi pada graf ,
Pembahasan utama pada artikel ini adalah terkait bilangan dominasi lokasi dari line pan graph dan middle  pan  graph .  Hasil  yang telah  diperoleh  dinyatakan  pada  Teorema  6 dan Teorema 8.
Teorema  6 Jika adalah  line  graph dari pan graph maka . Bukti: Diberikan graf dengani . Berdasarkan
definisi line graph dapat diketahui
sehingga Simpul
dan simpul
pada
mendominasi  3  simpul  dan  simpul  lainnya hanya mendominasi 2 simpul.
Kasus 1: untuk dan
Pada dan diperoleh  himpunan dominasi  yaitu .  Himpunan pada berlaku
dan  himpunan pada berlaku sehingga adalah  himpunan dominasi  lokasi  untuk dan dengan yang  merupakan  himpunan dominasi lokasi dengan kardinalitas minimum.  Akibatnya,  berdasarkan  Definisi 3, maka . Kasus 3: untuk Diberikan graf dan misalkan : (i) Untuk dan dengan diperoleh  himpunan  dominasi yaitu (ii) Untuk diperoleh himpunan dominasi, (iii) Untuk lainnya  himpunan  dominasi
dari , Setiap  himpunan , secara terurut
mempunyai  indeks  antar  simpul  dengan selisih 2 atau 3, akibatnya untuk
dengan diperoleh
dan . Berdasarkan , maka pada simpul-
simpul pada
mempunyai  indeks antar
simpul  dengan  selisih  1  atau  2  secara berurutan. Oleh karena itu, . Berdasarkan
Definisi  3,  maka  himpunan merupakan himpunan  dominasi  lokasi.  Selanjutnya, indeks-indeks  dari    dapat  dapat  dibentuk menjadi himpunan indeks:
Kardinalitas  masing-masing , dapat diperoleh dengan memanfaatkan rumus barisan  aritmatika.  Oleh  karena  itu,  untuk
, , diperoleh dan untuk lainnya. Dengan demikian, diperoleh . Selanjutnya, andaikan
.  Akibatnya,  untuk  simpul-
simpul  pada  himpunan  dominasi  lokasi
dengan simpul,  merupakan  simpul  yang mendominasi  2  simpul  disekitarnya  atau simpul yang mendominasi 3 simpul disekitarnya.  Oleh  karena  itu,  terdapat setidaknya  simpul di dengan
tetangga  sama  di dan  untuk ada
simpul  yang  tidak  terdominasi  (kontradiksi dengan  Definisi  3).  Jadi  dapat  disimpulkan
bahwa untuk . Contoh 7 Diberikan graf dan seperti yang terdapat di Gambar 3. (a) (b) Gambar 3. (a) Graf dan (b) Graf
Berdasarkan Gambar 3.(a), himpunan dominasi untuk graf yaitu dan dengan dan yang  berarti menjangkau  simpul-simpul di .  Diperoleh  juga  bahwa yang  artinya himpunan dominasi
lokasi dan
.  Hal  serupa  juga  berlaku
untuk  graf
pada  Gambar  3  (b),
dengan himpunan dominasi lokasinya
dan .
Teorema  8 Jika
adalah  middle
graph  dari  pan  graph  maka  diperoleh
. Bukti: Diberikan graf dengan . Menggunakan Definisi  1, mempunyai simpul dengan, . Derajat  simpul adalah  4  dan berderajat 5. Derajat simpul
adalah  2, berderajat
1, dan berderajat 3. Pilih , dengan  masing-masing
mendominasi  4  simpul  disekitarnya  dengan
mendominasi 5 simpul disekitarnya.  Akibatnya,  himpunan  berikut merupakan himpunan dominasi untuk yaitu: (i) untuk (ii)
untuk   lainnya.
Setiap  simpul minimal bertetangga  dengan  satu  simpul dengan pada ,  sehingga terdapat  setidaknya satu simpul yang mendominasi simpul . Akibatnya,  untuk dengan diperoleh . Setiap  simpul pada bertetangga dengan  simpul ,  dan  masing-
masing himpunan dominasi tersebut memiliki simpul-simpul secara terurut dengan  selisih  antar  indeks  adalah  1  atau  2 maka diperoleh . Untuk setiap simpul dengan bertetangga dengan simpul
dan setiap pada  salah  satu  himpunan  dominasi  yang dipilih memiliki indeks dengan selisih 1 atau 2  secara  terurut  maka  berakibat memiliki  tetangga  yang  berbeda  di dan
. Untuk setiap simpul yang  bertetangga  dengan  simpul
maka masing-masing
simpul  pada  himpunan memiliki  indeks selisih  1  atau  2.  Dengan  demikian,  masing- masing memiliki  tetangga  yang berbeda di . Karena bertetangga dengan simpul dan dengan bertetangga  dengan  simpul maka simpul minimal  didominasi  oleh
2  simpul  pada dan dengan minimal  didominasi  oleh  1 simpul  pada .  Untuk  simpul hanya
didominasi  oleh  simpul
dan  simpul bertetangga  dengan  simpul dan  masing-masing  simpul  secara  terurut
pada memiliki  indeks  selisih  1  atau  2
sehingga simpul minimal didominasi oleh 2 simpul pada . Akibatnya dengan
. Oleh karena itu,
merupakan  himpunan  dominasi  lokasi  dari
. Berdasarkan indeks-indeks simpul pada   diperoleh:
Kardinalitas masing-masing , dapat diperoleh  dengan  memanfaatkan  rumus barisan  aritmatika.  Oleh  karena  itu,  untuk
diperoleh dan untuk lainnya, . Akibatnya, berdasarkan Definisi 3, . Selanjutnya, andaikan , maka
himpunan  dominasi  lokasi  graf
memiliki
simpul.  Akibatnya,  untuk
graf ,  paling  tidak  terdapat  simpul dengan tetangga yang sama di (kontradiksi dengan Definisi 3). Jadi dapat disimpulkan bahwa . Contoh  9 Diberikan  graf seperti yang terdapat di Gambar 4.
Gambar 4. Middle Pan Graph
Berdasarkan  Gambar  4, merupakan  himpunan dominasi graf , simpul-simpul  yang  tidak  ada  di yaitu dan .  Berdasarkan  Gambar 4, , , , , dan .  Oleh
karena  itu,    menjangkau  simpul-simpul  di
. Diperoleh juga bahwa,
.  Dengan  demikian,    merupakan  himpunan dominasi  lokasi.  Oleh  karena himpunan dominasi  dengan  kardinalitas  minimum, maka diperoleh .

## KESIMPULAN
Berdasarkan  pembahasan  yang  telah dipaparkan,  bilangan  dominasi  lokasi  yang diperoleh  untuk line  pan  graph dan middle pan graph berturut-turut adalah dan .  Untuk , diperoleh bahwa . DAFTAR PUSTAKA Ayhan, A., & Omar, A. (2010).
Determination and Testing the Domination  Numbers  of  Tadpole Graph,  Book  Graph  and  Stacked Graph  Using  MATLAB. College  of Basic Education Researchers
Journal, 10 (1), 491-504.
Balbuena,  C.,  Foucaud,  F.,  &  Hansberg,  A.
(2015). Locating-dominating sets and indentifying codes  in graphs of Girth at  least  5. The  Electronic  Journal  of
Combinatorics, 22 (2), 1-15.
Canoy,  S.,  &  Malacas,  G.  (2014).  Locating- Dominating  sets  in  Graphs. Applied Mathematics  Sciences,  8 (88),  4381- 4388.
Chellali,  M.,  Mimouni,  M.,  &  Slater,  P.
(2010).  On  Locating-Domination  in Graphs. Discussiones  Mathematicae Graph Theory, 30 , 223-235.
Foucaud, F., Mertzios, G., R Naserasr, A. P.,
&  Valicov,  P.  (2016).  Indentification location-domination and metric
dimension  interval  and  permutation graph  II  Algorithms  and  complexity. Algorithmicai, 78 (3), 914-944.
Hernando,  C.,  Mora,  M.,  &  Pelayo,  M.
(2018).  Locating  Domination  in
Bipartite Graphs and their complements. Department de Matematiques, 2 , 1-15.
Kumar, K. (2011). Graph Theoretic Parameters  Applicable  to  Social Network. Math. Combin Book Series,
3 , 76-81.
Munir,  R.  (2010). Matematika  Diskrit.
Bandung: Informatika.
Murtaza, M., Fazil, M., Javaid, I., & Benish,
H.  (2017).  Locating-Dominating  Set of Functigraphs. Mathematics Subject Classification, 1 , 1-14.
Roza,  I.,  Narwen,  &  Zulakmal.  (2014).  Graf Garis dari Graf Siklus, Graf Lengkap dan Graf Bintang. Jurnal Matematika UNAND, 3 (2), 1-4.
Santoso,  B.,  Djuwandi,  &  Soelistyo,  R.
(2012). Bilangan dominasi dan bilangan  kebebasan  graf  bipartit kubik. Jurnal Matematika, 15 (1).
Sddiqui, N., & James, M. (2018).
Domination  and  Chromatic  Number of  Pan  Graph  and  Lollipop  Graph. International  Journal  of  Technical Innovation  in  Modern  Engineering and  Sciences(IJTIMES),  10 (1),  932- 939.
Vaidya, S., & Bantva, D. (2010). The L(2,1)-
Labeling  of  some  Middle  Graphs.
Journal of applied Computer
Sciences and Mathematics, 9 (4), 104-
107.
Yohana,  E.,  Yundari,  &  Fran,  F.  (2020).
Bilangan  dominasi  lokasi  pada  pan graph. Buletin  ilmiah  Matematika,
Statistika dan terapannya (Bimaster),
2 , 261-266.