ASIMETRIS: JURNAL PENDIDIKAN MATEMATIKA DAN SAINS p-ISSN 2721 – 8724, e-ISSN 2722 – 0214
Website Jurnal: http://journal.umuslim.ac.id/index.php/asm/
Info Artikel: Disubmit pada 24 April 2021 Direview pada 2 Mei 2021 Direvisi pada 11 Mei 2021
Diterima pada 12 Mei 2021 Tersedia secara daring pada 16 Mei 2021
DIMENSI METRIK PADA GRAF CALENDULA ( 𝑪𝒍 𝟑,𝒏 )
M. A. Shulhany 1 , Agusutrisno Agusutrisno 2 , Frena Fardillah 3 1,2 Jurusan Teknik Sipil, Fakultas Teknik, Universitas Sultan Ageng Tirtayasa
3 Jurusan Teknik Industri, Fakultas Teknik, Universitas Muhammadiyah Tangerang Alamat email: ahmad.s@untirta.ac.id
ABSTRAK. Semua graf 𝐺 = (𝑉 𝐺 , 𝐸 𝐺 ) yang dibahas pada penelitian ini merupakan graf tak-berarah, sederhana, dan berhingga. Misalkan 𝑠 adalah sebuah sisi graf 𝐻 . Hasil kali sisir sisi antara graf 𝐺 dan graf 𝐿 , dinotasikan dengan 𝐺 ⊵ 𝐿 , merupakan graf yang diperoleh dengan mengambil sebuah salinan 𝐺 dan |𝐸 𝐺 | buah salinan 𝐿 dan mencangkokkan sisi 𝑠 pada salinan ke- 𝑖 dari 𝐿 ke sisi ke- 𝑖 dari 𝐺 . Misalkan 𝑇 = (𝑡 1 , 𝑡 2 , … , 𝑡 𝑘 ) merupakan himpunan bagian terurut dari titik-titik pada 𝐺 yang anggota telah ditentukan.  Representasi  metrik  dari 𝑢 ∈ 𝑉 𝐺 terhadap 𝑇 ,  dan  dinotasikan  dengan  vektor 𝜆(𝑢|𝑇) = {𝑑(𝑢, 𝑡 1 ), 𝑑(𝑢, 𝑡 2 ), … , 𝑑(𝑢, 𝑡 𝑘 )} . Dimensi metrik pada 𝐺 adalah kardinalitas minimum dari semua himpunan 𝑇 pada 𝐺 sehingga 𝑟(𝑢 1 |𝑊) ≠ 𝑑(𝑢 2 |𝑊), dengan 𝑢 1 ≠ 𝑢 2 . Pada penelitian ini, dibahas dimensi matrik untuk graf calendula (𝐶𝑙 3,𝑛 ) . Kata Kunci: Dimensi metrik, Representasi metrik, Graf Calendula.
ABSTRACT. All graphs 𝐺  =   (𝑉 𝐺 , 𝐸 𝐺 ) in this study are undirected, simple, and finite graphs. Let 𝑠 be a edge of H. The edge- comb product between G and L, denoted 𝐺 ⊵ 𝐿 , is a graph obtained by taking one copy of 𝐺 and |𝐸 𝐺 | copies of 𝐿 and grafting 𝑠 in the i -th edge of 𝐿 to the 𝑖 -th edge of 𝐺 . Let 𝑇 = (𝑡 1 , 𝑡 2 , … , 𝑡 𝑘 ) be an ordered subset of vertices set in G that have been determined. The metric representation of 𝑢 ∈ 𝑉 𝐺 with respect to T, is denoted by 𝜆(𝑢|𝑇) = (𝑑(𝑢, 𝑡 1 ), 𝑑(𝑢, 𝑡 2 ), … , 𝑑(𝑢, 𝑡 𝑘 )) . The metric dimension of 𝐺 is the minimum cardinality of all sets 𝑇 in 𝐺 such that 𝑟(𝑢 1 |𝑊)   ≠  𝑑(𝑢 2 |𝑊) , which 𝑢 1 ≠ 𝑢 2 . This research discusses the metric dimensions of the marigold graphs (𝐶𝑙 3,𝑛 ) .
Keyword: Metric dimension, Metric representation, Marigold graphs

## I. PENDAHULUAN
Graf 𝐺 = (𝑉 𝐺 , 𝐸 𝐺 ) merupakan pasangan terurut himpunan titik 𝑉 𝐺 dan himpunan sisi 𝐸 𝐺 ⊆ [𝑉 𝐺 ] 2 . Semua graf yang dibahas pada penelitian ini  merupakan  graf  tak-berarah,  sederhana,  dan berhingga. Misalkan 𝑠 adalah sebuah sisi graf 𝐻 . Hasil  kali  sisir  sisi  antara  graf 𝐺 dan  graf 𝐿 , dinotasikan dengan 𝐺 ⊵ 𝐿 , merupakan graf yang diperoleh  dengan  mengambil  sebuah  salinan 𝐺 dan |𝐸 𝐺 | buah salinan 𝐿 dan mencangkokkan sisi 𝑠 pada  salinan  ke- 𝑖 dari 𝐿 ke  sisi  ke- 𝑖 dari 𝐺 (Dafik, dkk., 2017). Misalkan 𝑇 = (𝑡 1 , 𝑡 2 , … , 𝑡 𝑛 ) merupakan himpunan bagian teurut dari titik-titik graf 𝐺 yang anggota telah ditentukan. Representasi titik 𝑢 ∈ 𝑉 𝐺 terhadap 𝑇 ,  dinotasikan  dengan  vektor
𝜆(𝑢|𝑇) = {𝑑(𝑢, 𝑡 1 ), 𝑑(𝑢, 𝑡 2 ), … , 𝑑(𝑢, 𝑡 𝑛 )} . Himpunan 𝑊 disebut himpunan pemisah pada 𝐺 , jika  untuk  setiap  titik 𝑢, 𝑣 pada 𝑉 𝐺 dan 𝑢 ≠ 𝑣 mengakibatkan 𝜆(𝑢|𝑇) ≠ 𝜆(𝑣|𝑇) (Chartrand, dkk., 2000; Harary & Melter, 1976).
Dimensi metrik pada 𝐺 adalah kardinalitas minimum dari semua himpunan pemisah pada 𝐺 . Beberapa  hasil  penelitian  terkait  dimensi  metrik sebagai berikut:
Teorema  1 .  (Harary  &  Melter,  1976)  Graf 𝐺 berorde 𝑛 ≥ 2 yang memiliki dimensi metrik satu jika dan hanya jika 𝐺 adalah graf lintasan 𝑃 𝑛 .
Teorema  2 .  (Harary  &  Melter,  1976)  Graf 𝐺 berorde 𝑛 ≥ 2 yang memiliki dimensi metrik 𝑛 − 1 jika dan hanya jika 𝐺 adalah graf lengkap 𝐾 𝑛 .
Akibat  3 .  Jika 𝐺 berorde 𝑛 ≥ 2 ,  bukan  graf lengkap 𝐾 𝑛 , dan bukan graf lintasan 𝑃 𝑛 , maka
2 ≤ dim(𝐺) ≤ 𝑛 − 2.                                  (1)
Teorema  4 .  (Chartrand,  dkk.,  2000)  Graf 𝐺 berorde 𝑛 ≥ 4 yang memiliki dimensi metrik 𝑛 − 2 jika dan hanya jika 𝐺 = 𝐾 𝑠,𝑡 , dengan 𝑠, 𝑡 ≥ 1 atau 𝐺 = 𝐾 𝑠 + 𝐾 ̅ 𝑡 , atau 𝐺 = 𝐾 𝑠 + (𝐾 1 ∪ 𝐾 𝑡 ) , dengan 𝑠, 𝑡 ≥ 1 .
Teorema  5 .  (Chartrand,  dkk.,  2000)  Graf 𝐺 berorde 𝑛 ≥ 3 ,  berdiameter 𝑑 ,  dan 𝑓(𝑛, 𝑑) adalah  bilangan  positif 𝑘 terkecil  sehingga 𝑘 + 𝑑 𝑘 ≥ 𝑛 , maka
𝑓(𝑛, 𝑑) ≤ dim(𝐺) ≤ 𝑛 − 𝑑.                       (2)
Penelitian  lain  terkait  dimensi  matrik  yaitu Cáceres,  J.,  dkk  (2007)      meneliti  hasilkali Kartesian, Díaz, dkk (2012) dan Hauptmann, dkk (2012) meneliti kompleksitas dimensi metrik, Fehr, dkk  (2006)  meneliti  tentang  digraf  Cayley, Hernando,  dkk  (2010)  meneliti  dimensi  metrik dilihat  dari  teori  graf  ekstermal,  serta  Tomescu dan Javaid (2007)  meneliti graf Jahangir.

## II. METODE PENELITIAN
Metode penelitian yang digunakan adalah metode pencarian pola dengan langkah-langkah berikut:
a. Menentukan graf yang dianalisa
b. Menentukan  nama  titik-titik  di  graf  sehingga bisa diidentifikasi
c. Menentukan dugaan awal dari dimensi matrik graf
d. Membuat  pembuktian  awal  yang  berisi pembuktian batas bawah dan batas atas dari graf
e. Membuat kesimpulan dari pembuktian

## III. HASIL PENELITIAN DAN PEMBAHASAN
Pada penelitian ini, dibahas dimensi matrik untuk  graf  calendula (𝐶𝑙 3,𝑛 ) .  Misalkan 𝑛 merupakan  bilangan  asli  dengan 𝑛 ≥ 3 .
𝐺𝑟𝑎𝑓 𝑐𝑎𝑙𝑒𝑛𝑑𝑢𝑙𝑎 berorde 3𝑛 − 3 dinotasikan dengan 𝐶𝑙 3,𝑛 merupakan graf hasil kali sisir sisi dari  graf  lingkaran berorde 3 dan graf  lingkaran berorde 𝑛 ,  dinotasikan  dengan 𝐶 3 ⊵ 𝐶 𝑛 . Graf 𝐶𝑙 3,𝑛 merupakan graf dengan himpunan titik dan himpunan sisi masing-masing sebagai berikut:
𝑉(𝑆𝑓 𝑛 ) = {𝑣 𝑖 |1 ≤ 𝑖 ≤ 3𝑛 − 3}
𝐸(𝑆𝑓 𝑛 ) = {𝑣 𝑖 𝑣 𝑖+1 |1 ≤ 𝑖 ≤ 3𝑛 − 4} ∪ {𝑣 1 𝑣 3𝑛−3 } ∪ {𝑣 1 𝑣 𝑛 } ∪ {𝑣 1 𝑣 2𝑛−1 } ∪ {𝑣 𝑛 𝑣 2𝑛−1 }
Gambar 1. Ilustrasi graf 𝑆𝑓 𝑛 .
Teorema 6 . Misalkan 𝑛 ≥ 3 merupakan bilangan asli. Jika 𝐶𝑙 3,𝑛 merupakan graf calendula berorde 3𝑛 − 3 , maka dim(𝐶𝑙 3,𝑛 ) = 2.
Bukti. Misalkan 𝑛 ≥ 3 merupakan  bilangan  asli.  Graf 𝐶𝑙 3,𝑛 merupakan graf calendula berorde 3𝑛 − 3 . Pertama, akan ditunjukkan bahwa 𝑑𝑖𝑎𝑚(𝐶𝑙 3,𝑛 ) ≥ 2 .  Berdasarkan  Akibat  3,  kita peroleh 𝑑𝑖𝑎𝑚(𝐶𝑙 3,𝑛 ) ≥ 2 .  Kedua,  akan ditunjukkan  bahwa 𝑑𝑖𝑎𝑚(𝐶𝑙 3,𝑛 ) ≤ 2 dengan menentukan  sebuah  himpunan  pemisah  pada 𝐶𝑙 3,𝑛 dengan  2  titik.  Pilih  sebuah  himpunan pemisah 𝑇 = {𝑣 ⌈ 𝑛 2 ⌉ , 𝑣 ⌊ 3𝑛 2 ⌋ } .  Representasi  dari titik-titik 𝑣 𝑖 dengan 𝑇 adalah
1. 𝜆(𝑣 𝑖 |𝑇) = (⌈ 𝑛 2 ⌉ − 𝑖, ⌈ 𝑛 2 ⌉ + 𝑖 − 1), untuk 1 ≤ 𝑖 ≤ ⌊ 𝑛 2 ⌋ ; 2. 𝜆(𝑣 𝑖 |𝑇) = (𝑖 − ⌈ 𝑛 2 ⌉ , ⌊ 3𝑛 2 ⌋ − 𝑖), untuk ⌊ 𝑛 2 ⌋ + 1 ≤ 𝑖 ≤ ⌈ 3𝑛 2 ⌉ − 1 ; 3. 𝜆(𝑣 𝑖 |𝑇) = (⌈ 5𝑛 2 ⌉ − 𝑖 − 1, 𝑖 − ⌊ 3𝑛 2 ⌋), untuk ⌈ 3𝑛 2 ⌉ ≤ 𝑖 ≤ 2𝑛 − 1 ; 4. 𝜆(𝑣 𝑖 |𝑇) = (𝑖 − ⌊ 3𝑛 2 ⌋ + 1, 𝑖 − ⌊ 3𝑛 2 ⌋), untuk 2𝑛 ≤ 𝑖 ≤ ⌊ 5𝑛 2 ⌋ − 2 ; 5. 𝜆(𝑣 𝑖 |𝑇) = (𝑛 − 1, 𝑛 − 1), untuk 𝑖 = ⌊ 5𝑛 2 ⌋ − 1 dan bilangan ganjil 𝑛 ≥ 3 ; 6. 𝜆(𝑣 𝑖 |𝑇) = ( 1 2 (7𝑛 − 5) − 𝑖, 1
2 (7𝑛 − 3) −
𝑖), untuk ⌊ 5𝑛 2 ⌋ ≤ 𝑖 ≤ 3𝑛 − 3 dan bilangan ganjil 𝑛 ≥ 3 ; 7. 𝜆(𝑣 𝑖 |𝑇) = ( 1 2 (7𝑛 − 6) − 𝑖, 1 2 (7𝑛 − 4) −
𝑖), untuk ⌊ 5𝑛 2 ⌋ − 1 ≤ 𝑖 ≤ 3𝑛 − 3 dan bilangan genap 𝑛 ≥ 4 ;
Melalui  pemeriksaan  secara  langsung, terlihat  bahwa 𝜆(𝑢|𝑇) ≠ 𝜆(𝑣|𝑇) ,  untuk  setiap pasang titik 𝑢, 𝑣 ∈ 𝑉 𝐶𝑙 3,𝑛 , dan 𝑢 ≠ 𝑣 . Sehingga, himpunan 𝑇 merupakan himpunan pemisah. Dari pernyataan satu didapat 𝑑𝑖𝑎𝑚(𝐶𝑙 3,𝑛 ) ≥ 2 dan pernyataan dua didapat 𝑑𝑖𝑎𝑚(𝐶𝑙 3,𝑛 ) ≤ 2 , maka 𝑑𝑖𝑎𝑚(𝐶𝑙 3,𝑛 ) = 2 . ∎

## IV. SIMPULAN
Misalkan 𝑛 merupakan  bilangan  bulat positif  dan 𝑛 ≥ 3 .  Jika 𝐶𝑙 3,𝑛 merupakan  graf calendula  berorde 3𝑛 − 3 ,  maka  dimensi metriknya dim(𝐶𝑙 3,𝑛 ) = 2 .

## DAFTAR PUSTAKA
Cáceres, J., Hernando, C., Mora, M., Pelayo, I. M., Puertas,  M.  L.,  Seara,  C.,  &  Wood,  D.  R.
(2007). On the metric dimension of cartesian products of graphs. SIAM journal on discrete mathematics , 21 (2), 423–441. Chartrand,  G.,  Eroh,  L.,  Johnson,  M.  A.,  & Oellermann,  O.  R.  (2000).  Resolvability  in graphs and the metric dimension of a graph. Discrete  Applied  Mathematics , 105 (1–3), 99–113.
Dafik,  Agustin,  I.  H.,  Nurvitaningrum,  A.  I.,  &
Prihandini,  R.  M..  (2017).  On  super  H− antimagicness of an edge comb product of graphs  with  subgraph  as  a  terminal  of  its amalgamation. Journal of Physics: Conference Series , 855 (1), 12010. Díaz, J., Pottonen, O., Serna, M., & Van Leeuwen, E.  J.  (2012).  On  the  complexity  of  metric dimension. European  Symposium  on Algorithms , 419–430. Fehr,  M.,  Gosselin,  S.,  &  Oellermann,  O.  R. (2006).  The  metric  dimension  of  Cayley digraphs. Discrete mathematics , 306 (1), 31– 41.
Harary, F., & Melter, R. A. (1976). On the metric dimension  of  a  graph. Ars  combin , 2 (191– 195), 1.
Hauptmann,  M.,  Schmied,  R.,  &  Viehmann,  C.
(2012). Approximation complexity of metric dimension  problem. Journal  of  Discrete Algorithms , 14 , 214–222. Hernando, C., Mora, M., Pelayo, I. M., Seara, C.,
& Wood, D. R. (2010). Extremal graph theory for  metric  dimension  and  diameter. The Electronic  Journal  of  Combinatorics [electronic only] , 17 (1), Research-Paper. Tomescu,  I.,  &  Javaid,  I.  (2007).  On  the  metric dimension  of  the  Jahangir  graph. Bulletin mathématique  de  la  Société  des  Sciences Mathématiques de Roumanie , 371–376.