## DIMENSI METRIK LOKAL PADA GRAF ANTIPRISMA DAN GRAF SUN
1 Silfiatul Khoiriah, 2 Tri Atmojo Kusmayadi
1,2 Universitas Sebelas Maret Surakarta
Abstract: For  example  G  is  a  connected  and  nontrivial  graph.  The  distance  between two vertices u and v in G is the shortest path length between vertex  u and v  which is denoted by d (u, v). For an ordered set of 𝑾 = {𝒘 𝟏 , 𝒘 𝟐 , . . . , 𝒘 𝒏 } of n vertex and v is a vertex  in  G,  then  the  representation  of  vertex  v  to  W  is  an  ordered  pair 𝒓 𝒗 𝑾  = 𝒅 𝒗, 𝒘 𝟏 , 𝒅 𝒗, 𝒘 𝟐 , . . . , 𝒅 𝒗, 𝒘 𝒏 . Set  W  is  called  as  local  distinguishing  if 𝒓(𝒖|𝑾) ≠ 𝒓(𝒗|𝑾) for  each  pair  of  vertex  u  and  v  is  adjacent  to  G.  Local distinguishing  set  W  with  minimum  cardinality  is  called  as  local  metric  base  and  the number  of  vertex  on  the  local  metric  base  of  graph  G  is  called  as  local  metric dimension  which  is  denoted  by 𝐝𝐢𝐦 𝒍 (𝑮) .  In  this  study,  the  local  metric  dimension  is determined  on  antiprism  An  graph  and  sun  Sn  graph.  The  results  reveal  that  local metric  dimension  of  antiprism  graph  is 𝐝𝐢𝐦 𝒍 𝑨 𝒏 = 𝟑 for 𝒏  ≥ 𝟑 .  Local  metric dimension of sun graph is 𝐝𝐢𝐦 𝒍 𝑺 𝒏 = 𝟏 for even n and 𝐝𝐢𝐦 𝒍 𝑺 𝒏 = 𝟐 for odd n. Keywords: local  metric  dimension,  antiprism  graph,  sun  graph,  local  distinguishing set.

## PENDAHULUAN
Teori graf adalah salah satu cabang ilmu matematika yang mempelajari mengenai terminologi,  jenis,  dan  sifat  graf.  Menurut  Chartrand  dan  Lesniak,  suatu  graf 𝐺 adalah himpunan  tak  kosong  berhingga 𝑉 𝐺  =    𝑣 1 , 𝑣 2 , … , 𝑣 𝑛 yang  disebut  himpunan vertex dan 𝐸(𝐺)   =   {𝑒 1 , 𝑒 2 , . . . , 𝑒 𝑛 } merupakan  himpunan  pasangan  tidak  berurutan  dari anggota-anggota 𝑉 yang  disebut edge . Vertex merupakanrepresentasi  dari  titik  dan edge merupakan representasi dari garis. Teori grafdalam kegunaannya dapat diterapkan untuk menggambarkan  berbagai  macamstruktur  yang  ada  dengan  tujuan  sebagai  visualisasi objek agar menjadi mudahuntuk dipahami, seperti pada jaringan komunikasi, transportasi, riset operasi,dan  sebagainya.  Oleh  karena  itu, teori  graf  mengalami  perkembangan  yang begitu pesat.
Seiring perkembangan teori graf yang begitu pesat, muncul berbagai konsep baru, diantaranya  yaitu  dimensi  metrik  dari  suatu  graf  yang  diperkenalkan  oleh  Slater  pada tahun  1975.  Kemudian  pada  tahun  1976,  Harary  dan  Melter  secara  independen  juga memperkenalkan  konsep  yang  sama.  Misal 𝐺 adalah  suatu  graf  terhubung  nontrivial dengan  himpunan vertex 𝑉(𝐺) .  Suatu  himpunan 𝑊 ⊂  𝑉(𝐺) merupakan  himpunan pembeda  dari 𝐺 jika 𝑑(𝑢, 𝑥)   ≠  𝑑(𝑣, 𝑥) untuk  sembarang vertex 𝑢, 𝑣  ∈  𝑉(𝐺) dan beberapa  vertex 𝑥 ∈ 𝑊 ,  dimana 𝑑(𝑢, 𝑥) menyatakan  jarak,  yaitu  panjang  lintasan  ( path ) terpendek  dari vertex 𝑢 ke vertex 𝑥 .  Himpunan  pembeda  dengan  kardinalitas  terkecil disebut  himpunan  pembeda  minimum  atau  basis  dan  banyaknya  anggota  pada  basis disebut  dimensi  metrik.  Hingga  sekarang,  telah  muncul  beberapa  variasi  dari  himpunan
Journal of Mathematics and Mathematics Education                                              ISSN: 2089-8878 Vol.8, No.1, hal 9-15 Juli 2018 https://jurnal.uns.ac.id/jmme
pembeda,  dan  salah  satunya  yaitu  himpunan  pembeda  lokal  yang  diperkenalkan  oleh Okamoto et  al .  pada  tahun  2010.  Dimisalkan 𝑊  =   {𝑤 1 , 𝑤 2 , . . . , 𝑤 𝑘 } merupakan himpunan bagian dari himpunan vertex pada graf 𝐺 . Representasi suatu vertex 𝑢 pada graf 𝐺 terhadap 𝑊 merupakan pasangan berurutan dari jarak vertex 𝑢 dengan semua vertex di 𝑊 . Jarak dua vertex pada graf 𝐺 dideﬁnisikan sebagai panjang lintasan ( path ) terpendek dari satu vertex ke vertex lainnya. Himpunan 𝑊 disebut sebagai himpunan pembeda lokal jika  representasi  setiap  dua vertex yang  saling adjacent berbeda terhadap 𝑊 .  Himpunan pembeda lokal dengan jumlah anggota minimal disebut basis metrik lokal dan banyaknya anggota pada basis disebut dimensi metrik lokal.
Pada  tahun  2016,  Rodriguez-Velazquez et  al .  menentukan  dimensi  metrik  lokal pada  graf  hasil  operasi  korona.  Kemudian,  pada  tahun  2017  Cahyabudi  dan  Kusmayadi menentukan dimensi metrik lokal pada graf lollipop , graf web , dan graf friendship . Tahun 2018, Budianto dan Kusmayadi menentukan dimensi metrik lokal pada graf starbarbell, graf 𝐾 𝑚 ⊙ 𝑃 𝑛 ,  dan  graf 𝑀𝑜 𝑏𝑖𝑢𝑠 𝑙𝑎𝑑𝑑𝑒𝑟 .  Pada  tahun  yang  sama,  Solekhah  dan Kusmayadi menentukan dimensi metrik lokal pada graf t-fold wheel , graf 𝑃 𝑛 ⊙ 𝐾 𝑚 , dan graf generalized  fan. Penelitian  tersebut  dapat  digunakan  sebagai  acuan  dalam menentukan  dimensi  metrik  lokal  pada  kelas  graf  yang  lain.  Pada  penelitian  ini  akan dibahas mengenai dimensi metrik lokal pada graf antiprisma dan graf sun .

## METODE PENELITIAN
Metode  penelitian  yang  digunakan  dalam  penelitian  ini  adalah  kajian  pustaka yaitu  dengan  mengumpulkan  referensi  berupa  buku-buku  dan  jurnal.  Dari  metode  ini, penulis dapat menentukan dimensi metrik lokal pada graf antiprisma dan graf sun .
Langkah-langkah yang dilakukan dalam penelitian ini diuraikan sebagai berikut.
1. Menentukan 𝑊 pada graf antiprisma dan graf sun .
2. Menghitung jarak setiap vertex dengan 𝑊 yang telah ditentukan, sedemikian sehingga setiap  dua vertex berbeda  yang  saling adjacent pada  graf antiprisma dan  graf sun mempunyai representasi yang berbeda terhadap 𝑊 .
3. Menentukan  dimensi  metrik  lokal  dan  pola  umum  dimensi  metrik  lokal  pada  graf tersebut.
4. Membuat  pembuktian  dengan  menyusun  lema  dan  teorema  berdasarkan  hasil  yang diperoleh.
5. Membuat kesimpulan.

## HASIL DAN PEMBAHASAN
Pada  bab  ini  dibahas  dimensi  metrik  lokal  pada  graf antiprisma dan  graf sun sehingga diperoleh rumus umum dan disertai pembuktiannya.
A. Dimensi Metrik Lokal Pada graf antiprisma
Menurut Bac a et  al. graf antiprisma 𝐴 𝑛 dengan 𝑛 ≥ 3 adalah  suatu  graf  regular  ber- degree empat dengan jumlah vertex 2𝑛 dan jumlah edge 4𝑛 . Tersusun atas 𝐶 𝑛 luar dan dalam  kemudian  antara  kedua cycle dihubungkan  oleh edge 𝑣 𝑖 𝑢 𝑖 dan 𝑣 𝑖 𝑢 𝑖+𝑖(𝑚𝑜𝑑  𝑛) untuk 𝑖 = 1,2,3, … , 𝑛.
Sebuah  graf antiprisma 𝐴 𝑛 dengan  order 2𝑛 , size 4𝑛 , danhimpunan vertex 𝑉 𝐴 𝑛 = {𝑢 1 , 𝑢 2 , … , 𝑢 𝑛 , 𝑣 1 , 𝑣 2 , … , 𝑣 𝑛 } ditunjukkan pada Gambar 1.
Gambar 1 Graf antiprisma 𝑨 𝒏
Teorema 1.1. Jika 𝐴 𝑛 merupakan graf antiprisma, maka 𝑑𝑖𝑚 𝑙 𝐴 𝑛 = 3 .
Bukti. Misal  dipilih 𝑊 = {𝑢 1 , 𝑢 𝑛 , 𝑣 1 } adalah  himpunan  pembeda  lokal,  diperoleh representasi setiap vertex terhadap 𝑊 untuk 𝑛 genap adalah
𝑟(𝑢 𝑖 |𝑊) = 𝑖 − 1, 𝑖, 𝑖 ,                                  1 ≤ 𝑖 ≤ 𝑛 2 ; 𝑛 − 𝑖 + 1, 𝑛 − 𝑖, 𝑛 − 𝑖 + 1 , 𝑛 2 < 𝑖 < 𝑛. 𝑟(𝑣 𝑖 |𝑊) = 1,1,0 ,                                𝑖 = 1; 𝑖 − 1, 𝑖, 𝑖 − 1 ,                        2 ≤ 𝑖 ≤ 𝑛 2 ; 𝑖 − 1, 𝑖 − 1, 𝑖 − 1 ,                 𝑖 = 𝑛 + 1 2 ;
𝑛 − 𝑖 + 2, 𝑛 − 𝑖 + 1, 𝑛 𝑖 + 1 , 𝑛 + 1 2 < 𝑖 ≤ 𝑛.
dan untuk 𝑛 ganjil adalah
𝑟(𝑢 𝑖 |𝑊) 𝑖 − 1, 𝑖, 𝑖 ,                                   1 ≤ 𝑖 ≤ 𝑛 2 ;
𝑖 − 1, 𝑖 − 1, 1 ,                      𝑖 = 𝑛
2 ;
𝑛 − 𝑖 + 1, 𝑛 − 𝑖, 𝑛 − 𝑖 + 1 , 𝑛 2 < 𝑖 ≤ 𝑛.
𝑟(𝑣 𝑖 |𝑊)
1,1,0 ,                             𝑖 = 1; 𝑖 − 1, 𝑖, 𝑖 − 1 ,                            2 ≤ 𝑖 ≤ 𝑛 2 ;
𝑖 − 1, 𝑖 − 2, 𝑖 − 2 , 𝑛 2 ≤ 𝑖 ≤ 𝑛.
Setiap vertex 𝑉(𝐴 𝑛 ) memiliki  representasi  yang  berbeda  terhadap 𝑊 ,  sehingga 𝑊 adalah himpunan pembeda lokal dengan tiga elemen. Selanjutnya ditunjukkan bahwa 𝐴 𝑛 tidak memiliki himpunan pembeda lokal dengan 2 elemen.
Andaikan 𝐴 𝑛 memiliki himpunan pembeda 𝑊 dengan 2 elemen, pemilihan vertex dari
𝑊 ada tiga kemungkinan
1. Kedua vertex dari 𝑊 termasuk  dalam {𝑢 𝑖 : 1 ≤ 𝑖 ≤ 𝑛} ⊂ 𝑉(𝐴 𝑛 ) ,  misal  diambil 𝑊 = (𝑢 1 , 𝑢 2 ) diperoleh 𝑟 𝑢 𝑛 𝑊  = 𝑟 𝑣 1 = (1,2) .  Begitupun  jika  diambil sembarang  dua vertex 𝑢 𝑖 ∈ 𝑉(𝐴 𝑛 ) dengan 1 ≤ 𝑖 ≤ 𝑛 menjadi  himpunan 𝑊 ,  maka pasti  akan  terdapat  dua vertex pada 𝐴 𝑛 yang  memiliki  representasi  sama  terhadap 𝑊.
2. Kedua vertex dari 𝑊 termasuk  dalam {𝑣 𝑖 : 1 ≤ 𝑖 ≤ 𝑛} ⊂ 𝑉(𝐴 𝑛 ) ,  misal  diambil 𝑊 = (𝑣 1 , 𝑣 2 ) diperoleh 𝑟 𝑢 1 𝑊  = 𝑟 𝑣 𝑛 = (1,2) .  Begitupun  jika  diambil sembarang  dua vertex 𝑣 𝑖 ∈ 𝑉(𝐴 𝑛 ) dengan 1 ≤ 𝑖 ≤ 𝑛 menjadi  himpunan 𝑊 ,  maka pasti  akan  terdapat  dua vertex pada 𝐴 𝑛 yang  memiliki  representasi  sama  terhadap
𝑊.
3. Salah  satu vertex dari 𝑊 termasuk  dalam {𝑢 𝑖 : 1 ≤ 𝑖 ≤ 𝑛} ⊂ 𝑉(𝐴 𝑛 ) dan vertex lainnya  termauk  kedalam {𝑣 𝑖 : 1 ≤ 𝑖 ≤ 𝑛} ⊂ 𝑉(𝐴 𝑛 ) .  Misal  pada 𝐴 4 diambil 𝑊 = (𝑣 1 , 𝑢 1 ) diperoleh 𝑟 𝑢 3 𝑊  = 𝑟 𝑣 3 = (2,2) .  Begitupun  juka  diambil sembarang dua vertex dari 𝑢 𝑖 , 𝑣 𝑖 ∈ 𝑉(𝐴 𝑛 ) dengan 1 ≤ 𝑖 ≤ 𝑛 menjadi himpunan 𝑊 , maka  pasti  akan  terdapat  dua vertex pada 𝐴 𝑛 yang  memiliki  representasi  sama terhadap 𝑊.
Dari  kemungkinan  yang  ada,  diperoleh  hasil  yang  kontradiksi  dengan  pengandaian. Oleh  karena  itu 𝐴 𝑛 tidak  memiliki  himpunan  pembeda  lokal  dengan  dua  elemen  dan diperoleh  bahwa  himpunan  pembeda  lokal  pada 𝐴 𝑛 adalah  tiga  elemen,  sehingga dim 𝑙 𝐴 𝑛 = 3 .

## B. Dimensi Metrik Lokal Pada Graf Sun
Menurut  Mirzakhah  dan  Kiani.  Graf sun adalah  graf  yang  diperoleh  dengan menambahkan  satu  pasangan vertex dan edge dari  setiap vertex dalam  suatu cycle. Misalkan graf sun 𝑆 𝑛 mempunyai himpunan vertex 𝑉 𝑆 𝑛 = {𝑣 1 , 𝑣 2 , … , 𝑣 𝑛 , 𝑢 1 , 𝑢 2 , … , 𝑢 𝑛 } dengan 𝑛 ≥ 3 . Vertex-vertex 𝑣 1 , 𝑣 2 , … , 𝑣 𝑛 membentuk cycle dan vertex 𝑣 𝑖 adjacent dengan vertex pada 𝑢 𝑖 ,  dimana 1 ≤ 𝑖 ≤ 𝑛 . Bentuk umum graf sun dapat dilihat pada Gambar 2
Gambar 2 Graf sun 𝑺 𝒏
Berikut  diberikan  teorema  dari  Okamoto et  al. yang  digunakan  untuk mendukung teorema selanjutnya.
Teorema  1.2. Diberikan  graf 𝐺 adalah  graf  terhubung  nontrivial    ber-order 𝑛 ,  maka 𝑑𝑖𝑚 𝑙 𝐺  = 𝑛 − 1 jika dan hanya jika 𝐺 = 𝐾 𝑛 dan 𝑑𝑖𝑚 𝑙 (𝐺) = 1 jika dan hanya jika 𝐺 adalah graf bipartit.
Teorema 1.3. Jika 𝑆 𝑛 adalah suatu graf sun dengan 𝑛 ≥ 3 , maka 𝑑𝑖𝑚 𝑙 𝑆 𝑛 adalah 1,         𝑢𝑛𝑡𝑢𝑘 𝑛 𝑔𝑒𝑛𝑎𝑝; 2,         𝑢𝑛𝑡𝑢𝑘 𝑛 𝑔𝑎𝑛𝑗𝑖𝑙. Bukti. Diberikan graf sun 𝑆 𝑛 dengan himpunan vertex 𝑉 𝑆 𝑛 = {𝑣 1 , 𝑣 2 , … , 𝑣 𝑛 , 𝑢 1 , 𝑢 2 , … , 𝑢 𝑛 } . Dimensi mertik lokal pada graf sun terdiri atas dua kasus, yaitu untuk 𝑛 ganjil dan 𝑛 genap.
Kasus 1. Untuk 𝑛 genap
Misalkan  himpunan vertex pada 𝑆 𝑛 dipartisi  menjadi  dua  himpunan vertex yaitu 𝑉 1 =  𝑣 1 , 𝑣 3 , 𝑣 5 , … , 𝑣 𝑛−1 , 𝑢 2 , 𝑢 4 , 𝑢 6 , … , 𝑢 𝑛
dan 𝑉 1 = {𝑣 2 , 𝑣 4 , 𝑣 6 , … , 𝑣 𝑛 , 𝑢 1 , 𝑢 3 , 𝑢 5 , … , 𝑢 𝑛−1 } . Setiap vertex pada dua partisi tersebut tidak saling adjacent, yang berarti merupakan graf bipartit. Berdasarkan pada teorema 1.2. dapat disimpulkan bahwa dim 𝑙 𝑆 𝑛 = 1 untuk 𝑛 genap.
Kasus 2. Untuk 𝑛 ganjil
Misalkan  dipilih 𝑊 = {𝑣 𝑛 +1 2 , 𝑣 1 } ⊂ 𝑉(𝑆 𝑛 ) ,  diperoleh  representasi  setiap vertex terhadap 𝑊 adalah
𝑟(𝑢 𝑖 |𝑊) 𝑛 + 1
2 − 𝑖, 𝑖 − 1  ,      1 ≤ 𝑖 ≤ 𝑛 + 1 2 ; 𝑛 + 1 2 , 𝑛 − 𝑖 + 2 , 𝑛 + 1 2 < 𝑖 ≤ 𝑛.
𝑟(𝑣 𝑖 |𝑊) 𝑛 + 3 2 − 𝑖, 𝑖  ,       1 ≤ 𝑖 ≤ 𝑛 + 1
2 ;
( 𝑛 + 1 2 , 𝑛 − 𝑖 + 2), 𝑛 + 1 2 < 𝑖 ≤ 𝑛.
Karena setiap vertex yang saling adjacent pada 𝑆 𝑛 memiliki representasi yang berbeda terhadap 𝑊 sehingga 𝑊 merupakan  himpunan  pembeda  lokal  dengan  dua  elemen.
Berdasarkan pada teorema 1.2. yang menyatakan bahwa dim 𝑙 (𝐺) = 1 jika dan hanya jika 𝐺 adalah  graf bipartit, sedangkan  graf 𝑆 𝑛 dengan 𝑛 ganjil  tidak  dapat  dipartisi menjadi dua himpunan vertex sehingga bukan merupakan graf bipartit oleh sebab itu , terbukti benar bahwa himpunan pembeda lokal pada graf 𝑆 𝑛 adalah dua elemen, maka dim 𝑙 𝑆 𝑛 = 2 untuk 𝑛 ganjil.

## SIMPULAN DAN SARAN
Berdasarkan hasil dan pembahasan diperoleh kesimpulan sebagai berikut.
1. Dimensi metrik lokal pada graf antiprisma 𝐴 𝑛 dengan 𝑛 ≥ 3 adalah dim 𝑙 (𝐴 𝑛 ) = 3.
2. Dimensi  metrik  lokal  pada  graf sun 𝑆 𝑛 dengan 𝑛 ≥ 3 adalah  1  untuk 𝑛 genap  dan  2 untuk 𝑛 ganjil.
Penelitian ini  membahas  tentang  dimensi  metrik  lokal  pada  graf antiprisma dan graf sun . Bagi pembaca yangtertarik dengan topik ini, dapat mengembangkan penelitian dengan menerapkannya pada kelas-kelas graf lain misalnya graf helm atau graf sunflower .

## DAFTAR PUSTAKA
Bac a , M., F. Bashir, and A. Semanic ova . (2011). Face Antimagic Labeling of Antiprism. Util. Math, 84, 209-224.
Budianto, W.T., and T.A Kusmayadi. (2018). The Local Metric Dimension of starbarbell Graph, 𝐾 𝑚 ⊙ 𝑃 𝑛 graph  and Mo bius Ladder graph ,  Journal  of  Physics: conference Series 1008 012050 .
Cahyabudi,  A.  N.  and  T.  A.  Kusmayadi . (2017).On  The  Local  Metric  Dimension  of  A Lollipop  Graph,  A  Web  Graph,  and  A  Friendship  Graph .  Journal  of  Physics: Conference Series 909 012039 .
Chartrand,  G.,  and  L.  Lesniak.  (1979). Graphs  and  Digraphs, 2 𝑛𝑑 ed. California, Wadsworth Inc.
Harary,  F.  and  R.  A.  Melter  (1976).  On  The  Metric  Dimension  of  A  Graph .  Ars Combinatoria 2, 191-195.
Mirzakhah,  M.  and  D.  Kiani.  (2010).  The  Sun  Graph  is  Determined  by  Its  Signless Laplacian Spectrum . Electronic Journal of Linear Algebra 20, 610–620.
Okamoto,  F.,  B.  Phinezy,  P.  Zhang.  (2010).  The  Local  Metric  Dimension  of  A  Graph . Mathematica Bohemica 135(3), 239-255.
Rodr´ıguez-Vel´azquez, J. A., G. A. Barrag´an-Ram´ırez, and C. G. G´omez. (2016). On the Local Metric Dimension of Corona Product Graphs. Bull malays. Math. Sci. Soc. 39(2), 157-173.
Slater, P. J., Leaves of Trees. (1975). Congressus Numerantium 14, 549-559.
Solekhah, R.A., and T.A. Kusmayadi. (2017). On The Local Metric Dimension of t-Fold Wheel  Graph, 𝑃 𝑛 ⊙ 𝐾 𝑚 Graph,  and  Generalized  Fan  Graph. International Conference on Combinatoric, Graph Theory and Network Topology Universitas Negeri Jember .