Vol. 19, No. 2, January 2023, pp. 351-358 DOI: 10.20956/j.v19i2.23904

## The Partition Dimension on the Grid Graph

## Dimensi Partisi pada Graf Grid
Haspika 1* , Hasmawati 2* , Naimah Aris 3*
*Department of Mathematics, Faculty Mathematics and Natural Sciences, Hasanuddin University, Indonesia
E-mail: haspikafhika73@gmail.com 1 ;hasmaba97@gmail.com 2 ;newima@gmail.com 3 .
Received: 7 November 2022; Accepted: 20 December 2022; Published: 5 January 2023

## Abstract
Graph G is a discrete set pair with the notation 𝑉(𝐺) with its element called a vertex and the set of different and  unordered  pairs  with  the  notation 𝐸(𝐺) where  the  element  is  called  edge.  One  type  of  graph  is  a  grid graph  denoted 𝐺 𝑚,𝑛 ,  graph  of  the  result  of  the  operation  between  two  path  graphs (𝑃 𝑚 × 𝑃 𝑛 ) .    The  set  of partition ∏   = {𝑆 1 , 𝑆 2 , … , 𝑆 𝑘 } of 𝑉(𝐺) is called a resolving partition if its representation for each vertex in graph G is different. The value of 𝑘 is said to be the partition dimension of 𝐺 , if 𝑘 is the minimum value of the resolving partition ∏   = {𝑆 1 , 𝑆 2 , … , 𝑆 𝑘 } of 𝑉(𝐺). The partition dimension of the graph 𝐺 denoted with 𝑝𝑑(𝐺) . This paper discusses the dimension of the grid graph partition 𝐺 𝑚,𝑛 with the result 𝑝𝑑(𝐺 𝑚,𝑛 ) = 3 for 𝑚, 𝑛 ≥ 2 with 𝑛 even value. Keywords: graph grid, partition dimensions, set of resolving partition, the lower and upper bound

## Abstrak
Graf 𝐺 adalah  pasangan  himpunan  diskrit  dengan  notasi 𝑉(𝐺) yang  anggotanya  disebut  titik  dan  himpunan pasangan-pasangan tak terurut dan berbeda dengan notasi 𝐸(𝐺) yang anggotanya disebut sisi. Salah satu jenis graf adalah graf grid yang diberi notasi 𝐺 𝑚,𝑛 , suatu graf hasil operasi kali antara dua graf lintasan (𝑃 𝑚 × 𝑃 𝑛 ) . Himpunan partisi ∏   = {𝑆 1 , 𝑆 2 , … , 𝑆 𝑘 } dari 𝑉(𝐺) disebut partisi pembeda jika representasinya  untuk setiap titik yang ada pada graf 𝐺 berbeda. Nilai 𝑘 dikatakan dimensi partisi dari 𝐺 , jika 𝑘 merupakan nilai minimum partisi pembeda ∏   = {𝑆 1 , 𝑆 2 , … , 𝑆 𝑘 } dari 𝑉(𝐺). Dimensi partisi dari 𝐺 dinotasikan dengan 𝑝𝑑(𝐺) . Tulisan ini membahas dimensi partisi graf grid 𝐺 𝑚,𝑛 dengan hasil 𝑝𝑑(𝐺 𝑚,𝑛 ) = 3 untuk 𝑚, 𝑛 ≥ 2 dan 𝑛 bernilai genap Kata Kunci: graf grid, dimensi partisi, himpunan partisi pembeda, batas bawah dan batas atas

## 1. Pendahuluan
Teori  graf  merupakan  salah  satu  cabang  ilmu  matematika  yang  sangat  bermanfaat  untuk membantu  menyelesaikan  suatu  permasalahan  dalam  kehidupan  nyata.  Mempresentasikan permasalahan ke dalam bentuk graf, akan membuat permasalahan tersebut lebih mudah dimengerti dan  lebih  mudah  mencari  solusinya.  Salah  satu  topik  yang  menjadi  kajian  penelitian dalam  teori graf  adalah  dimensi  metrik  dan  dimensi  partisi.  Dimensi  metrik  diperkenalkan  pertama  kali  oleh Harry  dan  Melter  pada  tahun  1966.  Dimensi  metrik  tidak  mudah  untuk  diperoleh  dari  suatu  graf tertentu. Oleh karena itu, untuk memperoleh dimensi metrik graf tertentu maka dilakukan analisis

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI

## Haspika, Hasmawati, Naimah Aris
dari  subgraf  terlebih  dahulu  untuk  memudahkan  mendapatkan  dimensi  metrik  dari  graf  secara umum  [12].  Dimensi  metrik  dapat  digunakan  untuk  pembahasan  pada  bidang  lain  seperti  kimia, navigasi  robot  dan  pencarian  [9]  dan  optimasi  kombinasi  [7].  Untuk  mendapatkan  cara  pandang baru  dalam  mendalami  dimensi  metrik  graf,  Chartrand,  dkk  (2000)  memperkenalkan  konsep  baru disebut dimensi partisi graf.
Graf  adalah  pasangan  himpunan  terurut (𝑉, 𝐸) ,  dan  ditulis  dengan  notasi 𝐺 = (𝑉, 𝐸) , dengan 𝑉 adalah  himpunan  tidak  kosong  yang  anggotanya  disebut  titik  dan 𝐸 adalah  himpunan pasangan-pasangan  tidak  terurut  dari  anggota 𝑉 yang  disebut  sisi.  Menurut  Chartrand,  himpunan titik pada graf 𝐺 dapat dibagi  menjadi beberapa himpunan partisi 𝑆 . Himpunan 𝛱 dengan 𝑆  ∈  𝛱 disebut  himpunan  pembeda  dari  graf 𝐺 jika  setiap  titik  di 𝐺 mempunyai  representasi  berbeda terhadap 𝛱 , dan 𝛱 merupakan himpunan dari k-partisi yang terurut. Kardinalitas minimum dari k- partisi pembeda terhadap 𝑉(𝐺) adalah dimensi partisi pada graf 𝐺 yang dinotasikan dengan 𝑝𝑑(𝐺) . Hasil  pada  paper  [1]  menunjukkan  bahwa  dimensi  partisi  graf  lintasan  adalah 𝑝𝑑(𝑃 𝑛 ) = 2 dan dimensi  partisi  graf lengkap  adalah 𝑝𝑑(𝐾 𝑛 ) = 𝑛 .  Selanjutnya,  dimensi  partisi  telah  banyak  dikaji oleh  peneliti,  misalnya  [4]  menunjukan  dimensi  partisi  dari  kelas  graf  circulant,  [8]  menujukkan dimensi partisi dari beberapa kelas graf pohon dan [2] juga menunjukkan dimensi partisi dari graf multipartit dan graf hasil korona dari dua graf terhubung.
Salah satu contoh graf dalam teori graf adalah graf grid, yang merupakan hasil kali antara graf lintasan orde 𝑛 dan orde 𝑚 . Dikarenakan dari beberapa hasil penelitian sebelumnya belum ada yang  membahas  tentang  dimensi  partisi  pada  graf  grid,  maka  dalam  penelitian  ini  penulis  akan menganalisis dimensi partisi pada graf grid.

## 2. Tinjauan pustaka
Secara  umum  dikenal  beberapa  macam  pengertian  graf.  Pada  [5]  graf  adalah  pasangan himpunan (𝑉, 𝐸) , dengan 𝑉 adalah himpunan diskrit yang anggota-anggotanya disebut titik, dan 𝐸 adalah himpunan  dari  pasangan  anggota-anggota 𝑉 yang  disebut sisi.  Jika  graf (𝑉, 𝐸) dinotasikan 𝐺 , dengan kata lain 𝐺 = (𝑉, 𝐸) , maka 𝑉 = 𝑉(𝐺) dan 𝐸 = 𝐸(𝐺) , sehingga graf 𝐺 = (𝑉(𝐺), 𝐸(𝐺)) . graf 𝐺 = (𝑉, 𝐸) , jika 𝑢, 𝑣 ∈ 𝑉 dengan 𝑢 ≠ 𝑣 dan 𝑢𝑣 = 𝑣𝑢 maka graf 𝐺 merupakan graf sederhana ( simple  graph ).  Barisan  titik  dan  sisi 𝑣 1 , 𝑒 1 , 𝑣 2 , 𝑒 2 , … 𝑣 𝑛−1 , 𝑒 𝑛−1 , 𝑣 𝑛 dengan 𝑒 𝑖 = 𝑣 𝑖 𝑣 𝑖+1 , 𝑖 = 1,2,3, … , 𝑛 − 1 disebut lintasan  pada  graf.  Graf  yang  hanya  memiliki  sebuah  lintasan  disebut  graf lintasan yang dinotasikan 𝑃 𝑛 untuk orde 𝑛 .
Dalam graf dikenal beberapa operasi salah satu  diantaranya adalah operasi perkalian graf. Misalkan 𝐺 adalah  graf  dengan  himpunan  titik 𝑉(𝐺) dan  himpunan  sisi 𝐸(𝐺) dan 𝐻 adalah  graf dengan  himpunan  titik 𝑉(𝐻) dan  himpunan  sisi 𝐸(𝐻) ,  maka  graf  kali 𝐺 × 𝐻 adalah  graf  dengan graf  titik 𝑉(𝐺 × 𝐻) = 𝑉(𝐺) × 𝑉(𝐻) dan  himpunan  sisi 𝐸(𝐺 × 𝐻) = {𝑥𝑦|𝑥 = 𝑢 1 𝑣 1 , 𝑦 = 𝑢 2 𝑣 2 ; 𝑢 1 = 𝑢 2 dan 𝑣 1 𝑣 2 ∈ 𝐸(𝐻) atau 𝑣 1 = 𝑣 2 dan 𝑢 1 𝑢 2 ∈ 𝐸(𝐺)} [5]. Melalui  operasi  dalam  graf bisa dihasilkan suatu jenis graf baru.  Contohnya pada operasi perkalian atara dua graf lintasan yang menghasilkan graf grid. Pada [13] graf grid adalah graf hasil kali dari graf lintasan (𝑃 𝑚 × 𝑃 𝑛 ).
Partisi  dari  sebuah  himpunan 𝑆 adalah  dekomposisi  dari 𝑆 ke  dalam  subset-subset  tak kosong atau cell S 1 , 𝑆 2 , … , 𝑆 𝑛 sedemikian sehingga :
a) S 𝑖 ≠ ∅ untuk setiap 𝑖 = 1,2, … . , 𝑛 .
b) S 𝑖 ∩ 𝑆 𝑗 = ∅ untuk setiap i ≠ j, 𝑖, 𝑗 = 1,2, … . , 𝑛 .
c) S 1 ∪ 𝑆 2 ∪ … ∪ 𝑆 𝑛 = 𝑆 . Dengan demikian, cell dari partisi disjoint . [15].
Dimensi partisi dari suatu graf 𝐺 pertama kali dikenalkan oleh Chartrand, Salehi dan Zhang (2000). Mereka mengelompokkan semua titik yang ada pada graf 𝐺 ke sejumlah kelas partisi dan menentukan jarak setiap simpul ke partisi tersebut.
Misalkan terdapat sebuah graf terhubung 𝐺 dengan 𝑉(𝐺) adalah himpunan titik-titiknya, 𝑆 adalah  himpunan  bagian  dari 𝑉(𝐺) dan 𝑣 titik  di 𝐺 ,  jarak  antara 𝑣 dan 𝑆 didefinisikan  sebagai 𝑑(𝑣, 𝑆) = 𝑚𝑖𝑛{𝑑(𝑣, 𝑥)|𝑥 ∈ 𝑆}. Misalkan  terdapat  sebuah  graf  terhubung 𝐺 dan  koleksi  himpunan ∏   = {𝑆 1 , 𝑆 2 , … , 𝑆 𝑘 } ,  dengan 𝑆 𝑗 merupakan  partisi  dari 𝑉(𝐺) .  Himpunan ∏   = {𝑆 1 , 𝑆 2 , … , 𝑆 𝑘 } disebut himpunan partisi dan 𝑆 𝑗 disebut kelas partisi.  Misalkan 𝑣 titik di 𝐺 , representasi 𝑣 terhadap

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI

## Haspika, Hasmawati, Naimah Aris
∏ didefinisikan  sebagai 𝑟(𝑣| ∏  ) = (𝑑(𝑣, 𝑆 1 ), 𝑑(𝑣, 𝑆 2 ), … , 𝑑(𝑣, 𝑆 𝑘 )) .  Himpunan  partisi ∏   = {𝑆 1 , 𝑆 2 , … , 𝑆 𝑘 } dikatakan partisi pembeda, jika representasnya untuk setiap titik yang ada pada graf 𝐺 berbeda.  Nilai 𝑘 dikatakan  dimensi  partisi  dari 𝐺 ,  jika 𝑘 merupakan  nilai  minimum  partisi pembeda ∏   = {𝑆 1 , 𝑆 2 , … , 𝑆 𝑘 } dari 𝑉(𝐺). Dimensi partisi dari 𝐺 dinotasikan dengan 𝑝𝑑(𝐺) .
Teorema 2.1 Misalkan 𝐺 adalah graf terhubung dengan orde 𝑛 ≥ 2 .
(i). 𝑝𝑑(𝐺) = 2 jika dan hanya jika 𝐺 = 𝑃 𝑛 (ii). 𝑝𝑑(𝐺) = 𝑛 jika dan hanya jika 𝐺 = 𝐾 𝑛 (iii). Untuk 𝑛 ≥ 4 , 𝑝𝑑(𝐺) = 𝑛 − 1 jika  dan  hanya  jika 𝐺 = 𝐾 𝑟,𝑠 , (𝑟, 𝑠 ≥ 1, 𝐺 = 𝐾 𝑟 + 𝐾 𝑠 ̅̅̅, (𝑟 ≥ 1, 𝑠 ≥ 2), 𝑜𝑟 𝐺 = 𝐾 𝑟 + (𝐾 1 ∪ 𝐾 𝑠 ), (𝑟, 𝑠 ≥ 1).

## 3. Hasil Utama
Hasil utama yang dibahas dalam makalah ini adalah konstruksi graf grid, batas bawah dan batas  atas  dimensi  partisi  graf  grid,  dan  juga  dimensi  partisi  pada  graf  grid,  yang  disajikan  pada Teorema  3.1.  Beberapa  pernyataan  yang  cukup  membantu  dalam  membuktikan  Teorema  3.1 disajikan dalam bentuk Proposisi 3.1 sampai Proposisi 3.4.

## Konstruksi Graf Grid
Perkalian dua graf lintasan merupakan operasi graf yang menghasilkan graf baru yaitu graf grid,  Diberikan  dua  graf  lintasan 𝑃 𝑚 dan 𝑃 𝑛 dengan 𝑛 bernilai  genap  maka  graf  grid 𝑃 𝑚 × 𝑃 𝑛 mempunyai himpunan titik 𝑉(𝑃 𝑚 × 𝑃 𝑛 ) = {𝑤 𝑖,𝑗 |1 ≤ 𝑖 ≤ 𝑚, 1 ≤ 𝑗 ≤ 𝑛} dan himpunan sisi 𝐸(𝑃 𝑚 × 𝑃 𝑛 ) = {𝑤 𝑖,𝑗 𝑤 𝑖,𝑗+1 ; 𝑤 𝑖,𝑗 𝑤 𝑖+1,𝑗 |1 ≤ 𝑖 ≤ 𝑚, 1 ≤ 𝑗 ≤ 𝑛} .  Graf  hasil  kali 𝑃 𝑚 × 𝑃 𝑛 dapat  digambarkan sebagai berikut:
Proposisi 3.1 Diberikan graf terhubung 𝐺 2,2 , maka dimensi partisi graf 𝐺 2,2 adalah 𝑝𝑑(𝐺 2,2 ) = 3 .
Bukti:
Diberikan graf 𝐺 2,2 dengan himpunan titik 𝑉(𝐺 2,2 ) = {𝑤 1,1 , 𝑤 1,2 , 𝑤 2,1 , 𝑤 2,2 } dan himpunan sisi 𝐸(𝐺 2,2 ) = { 𝑤 1,1 𝑤 1,2 , 𝑤 1,1 𝑤 2,1 , 𝑤 1,2 𝑤 2,2 , 𝑤 2,1 𝑤 2,2 } seperti pada gambar dibawah:
Merujuk pada Teorema 2.1(i) yang menyatakan bahwa 𝑝𝑑(𝐺) = 2 jika dan hanya jika 𝐺 = 𝑃 𝑛 atau 𝐺 ≅ 𝑃 𝑛 .  Pada  teorema  ini  diperoleh  kontraposisinya  yaitu 𝑝𝑑(𝐺) ≠ 2 jika  dan  hanya  jika 𝐺 ≠ 𝑃 𝑛 dan 𝐺 ≇ 𝑃 𝑛 .  Karena 𝐺 𝑚,𝑛 ≠ 𝑃 𝑛 dan 𝐺 𝑚,𝑛 ≇ 𝑃 𝑛 maka  diperoleh  dimensi  partisi  graf 𝐺 adalah 𝑝𝑑(𝐺) ≠ 2 atau dapat ditulis 𝑝𝑑(𝐺 2,2 ) ≥ 3 .
… (3.1)
Gambar 3.1. Graf 𝑃 𝑚 × 𝑃 𝑛 dengan 𝑛
bernilai genap 𝑤 2,𝑛 𝑤 1,𝑛 𝑤 4,𝑛 𝑤 3,𝑛 𝑤 𝑚,𝑛 𝑤 1,4 𝑤 1,1 𝑤 2,𝑛−1 𝑤 1,2 𝑤 1,𝑛−1 𝑤 4,𝑛−1 𝑤 1,3 𝑤 3,𝑛−1 𝑤 𝑚,𝑛−1
𝑃 𝑚 × 𝑃 𝑛 : 𝑤 2,1 𝑤 3,1 𝑤 4,1 𝑤 𝑚,1 𝑤 2,2
𝑤 3,2 𝑤 4,2 𝑤 𝑚,2 𝑤 𝑚,3 𝑤 4,3 𝑤 3,3 𝑤 2,3 𝑤 2,4 𝑤 3,4 𝑤 4,4 𝑤 𝑚,4 Gambar 3.2 . Graf 𝐺 2,2 𝑤 1,1 𝑤 1,2
𝐺 2,2 : 𝑤 2,1 𝑤 2,2

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI

## Haspika, Hasmawati, Naimah Aris
Selanjutnya  akan  dicari  batas  atas  Graf 𝐺 2,2 .  Pilih  himpunan  partisi ∏ = {𝑆 1 , 𝑆 2 , 𝑆 3 } dengan 𝑆 1 = {𝑤 1,1 } , 𝑆 2 = {𝑤 2,1 } dan 𝑆 3 = {𝑤 1,2 , 𝑤 2,2 } .  Refresetasi  setiap  titik  di 𝐺 2,2 terhadap ∏ sebagai berikut: 𝑟( 𝑤 1,1 | ∏ ) = (0,1,1) 𝑟( 𝑤 2,1 | ∏ ) = (1,0,1) 𝑟( 𝑤 1,2 | ∏ ) = (1,2,0) 𝑟( 𝑤 2,2 | ∏ ) = (2,1,0)
Terlihat dari hasil observasi di atas, semua titik dari graf 𝐺 2,2 mempunyai representasi yang berbeda,  sehingga ∏ = {𝑆 1 , 𝑆 2 , 𝑆 3 } merupakan  partisi  pembeda  dari  graf 𝐺 2,2 dengan  kardinalitas | ∏ |  = 3 . Jadi, 𝑝𝑑(𝐺 2,2 ) ≤ 3 . … (3.2)
Berdasarkan persamaan (3.1) dan (3.2) diperoleh batas atas dan batas bawah dimensi partisi 𝐺 2,2 adalah 3 ≤ 𝑝𝑑(𝐺 2,2 ) ≤ 3 , jadi, dimensi partisi graf 𝐺 2,2 adalah 𝑝𝑑(𝐺 2,2 ) = 3 . ∎
Proposisi 3.2 Diberikan graf sederhana 𝐺 3,2 , maka dimensi partisi graf 𝐺 3,2 adalah 𝑝𝑑(𝐺 3,2 ) = 3 . Bukti:
Diberikan graf 𝐺 3,2 dengan himpunan titik 𝑉(𝐺 3,2 ) = {𝑤 1,1 , 𝑤 1,2 , 𝑤 2,1 , 𝑤 2,2 , 𝑤 3,1 , 𝑤 3,2 } dan himpunan  sisi 𝐸(𝐺 3,2 ) = { 𝑤 1,1 𝑤 1,2 , 𝑤 1,1 𝑤 2,1 , 𝑤 1,2 𝑤 2,2 , 𝑤 2,1 𝑤 2,2 , 𝑤 2,1 𝑤 3,1 , 𝑤 2,2 𝑤 3,2 , 𝑤 3,1 𝑤 3,2 } seperti pada gambar dibawah:
Batas  bawah  dari  graf 𝐺 3,2 dapat  diperoleh  dengan  cara  yang  sama  dengan  menentukan batas  bawah  graf 𝐺 2,2 pada  Proposisi  3.1  sehingga  diperoleh  batas  bawah  dari  graf 𝐺 3,2 adalah 𝑝𝑑(𝐺 3,2 ) ≥ 3 . … (3.3)
Selanjutnya akan dicari batas atas dari graf 𝐺 3,2 . Untuk mencari batas atas dimensi partisi dari  graf 𝐺 3,2 dapat  diperoleh  dengan  mengkontruksi  partisi  pembeda ∏ . Ambil  partisi  pembeda ∏ = {𝑆 1 , 𝑆 2 , 𝑆 3 } dengan 𝑆 1 = {𝑤 1,1 } , 𝑆 2 = {𝑤 2,1 , 𝑤 3,1 } dan 𝑆 3 = {𝑤 1,2 , 𝑤 2,2 , 𝑤 3,2 } ,  sehingga diperoleh representasi untuk setiap titik di 𝐺 3,2 terhadap ∏ sebagai berikut: 𝑟( 𝑤 1,1 | ∏ ) = (0,1,1) ,
𝑟( 𝑤 2,1 | ∏ ) = (1,0,1) ,
𝑟( 𝑤 3,1 | ∏ ) = (2,0,1) , 𝑟( 𝑤 1,2 | ∏ ) = (1,2,0) , 𝑟( 𝑤 2,2 | ∏ ) = (2,1,0) ,
𝑟( 𝑤 3,2 | ∏ ) = (3,1,0) . Dari hasil observasi diatas dapat dilihat bahwa setiap titik di graf 𝐺 3,2 terhadap ∏ berbeda dengan  kardinalitas | ∏ | = 3 ,  sehingga  diperoleh  batas  atas  dimensi  partisi  graf 𝐺 3,2 adalah 𝑝𝑑(𝐺 3,2 ) ≤ 3 . … (3.4)
Berdasarkan persamaan (3.3) dan (3.4) diperoleh batas atas dan batas bawah dimensi partisi graf 𝐺 3,2 adalah 3 ≤ 𝑝𝑑(𝐺 3,2 ) ≤ 3 . Jadi dimensi partisi graf 𝐺 3,2 adalah 𝑝𝑑(𝐺 3,2 ) = 3 . ∎
Proposisi 3.3 Diberikan graf sederhana 𝐺 3,4 maka dimensi partisi graf 𝐺 3,4 adalah 𝑝𝑑(𝐺 3,4 ) = 3 . Bukti:
Diberikan  graf 𝐺 3,4 dengan  himpunan  titik 𝑉(𝐺 3,4 ) = {𝑤 1,1 , 𝑤 1,2 , 𝑤 1,3 , 𝑤 1,4 , 𝑤 2,1 , 𝑤 2,2 , 𝑤 2,3 , 𝑤 2,4 , 𝑤 3,1 , 𝑤 3,2 , 𝑤 3,3 , 𝑤 3,4 } dan himpunan sisi 𝐸(𝐺 3,4 ) = {𝑤 1,1 𝑤 1,2 , 𝑤 1,1 𝑤 2,1 , 𝑤 1,2 𝑤 1,3 , 𝑤 1,2 𝑤 2,2 , 𝑤 1,3 𝑤 1,4 , 𝑤 1,3 𝑤 2,3 , 𝑤 1,4 𝑤 2,4 , 𝑤 2,1 𝑤 2,2 , 𝑤 2,1 𝑤 3,1 , 𝑤 2,2 𝑤 2,3 , 𝑤 2,2 𝑤 3,2 , 𝑤 2,3 𝑤 2,4 , 𝑤 2,3 𝑤 3,3 , 𝑤 2,4 𝑤 3,4 , 𝑤 3,1 𝑤 3,2 , 𝑤 3,2 𝑤 3,3 , 𝑤 3,3 𝑤 3,4 } seperti pada gambar dibawah ini,
𝑤 3,1 𝑤 3,2 Gambar 3.3. Graf 𝐺 3,2 𝑤 1,1 𝑤 1,2
𝐺 3,2 : 𝑤 2,1 𝑤 2,2

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI

## Haspika, Hasmawati, Naimah Aris
Penentuan  batas  bawah  dimensi  partisi  pada  graf 𝐺 3,4 dapat  diperoleh  dengan  cara  yang sama  pada  Proposisi  3.1  dengan  menggunakan  Teorema  2.1(i),  sehingga  diperoleh  batas  bawah dimensi partisi pada graf 𝐺 3,4 adalah 𝑝𝑑(𝐺 3,4 ) ≥ 3 . … (3.5)
Selanjutnya  untuk  mencari  batas  atas  dimensi  partisi  graf 𝐺 3,4 dengan  cara  yang  sama dengan  Proposisi  3.2  yaitu  mengkontruksi  partisi  pembeda ∏ . Ambil ∏ = {𝑆 1 , 𝑆 2 , 𝑆 3 } dengan 𝑆 1 dan 𝑆 2 sama  dengan  yang  ada  pada  Proposisi  3.2    dan 𝑆 3 = {𝑤 1,2 , 𝑤 1,3 , 𝑤 1,4 , 𝑤 2,2 , 𝑤 2,3 , 𝑤 2,4 , 𝑤 3,2 , 𝑤 3,3 , 𝑤 3,4 } .  Akan  ditunjukan  bahwa  representasi  setiap  titik  di  graf 𝐺 3,4 terhadap ∏ berbeda. Sedangkan pada titik lainnya yaitu: 𝑟( 𝑤 1,1 | ∏ ) = (0,1,1) ,
𝑟( 𝑤 1,2 | ∏ ) = (1,2,0) ,
𝑟( 𝑤 1,3 | ∏ ) = (2,3,0) ,
𝑟( 𝑤 1,4 | ∏ ) = (3,4,0) ,
𝑟( 𝑤 2,1 | ∏ ) = (1,0,1) , 𝑟( 𝑤 2,2 | ∏ ) = (2,1,0) ,
𝑟( 𝑤 2,3 | ∏ ) = (3,2,0) , 𝑟( 𝑤 2,4 | ∏ ) = (4,3,0) ,
𝑟( 𝑤 3,1 | ∏ ) = (2,0,1) ,
𝑟( 𝑤 3,2 | ∏ ) = (3,1,0) .
𝑟( 𝑤 3,3 | ∏ ) = (4,2,0) ,
𝑟( 𝑤 3,4 | ∏ ) = (5,3,0) . Terlihat dari hasil observasi diatas, semua titik pada graf 𝐺 3,4 memiliki representasi berbeda dengan  kardinalitas | ∏ | = 3, sehingga  diperoleh  batas  atas  dimensi  partisi  graf 𝐺 3,4 adalah 𝑝𝑑(𝐺 3,4 ) ≤ 3 .
… (3.6)
Berdasarkan persamaan (3.5) dan (3.6) diperoleh batas atas dan batas bawah dimensi partisi graf 𝐺 3,4 adalah 3 ≤ 𝑝𝑑(𝐺 3,4 ) ≤ 3 ,  sehimgga  diperoleh  dimensi  partisi  dari  graf 𝐺 3,4 adalah 𝑝𝑑(𝐺 3,4 ) = 3 . ∎
Proposisi 3.4 Jika 𝑚 ≥ 2 , maka dimensi partisi graf 𝐺 𝑚,2 adalah 𝑝𝑑(𝐺 𝑚,2 ) = 3 Bukti:
Misalkan  graf 𝐺 𝑚,2 dengan  himpunan  titik 𝑉(𝐺 𝑚,2 ) = {𝑤 𝑖,𝑗 |1 ≤ 𝑖 ≤ 𝑚, 1 ≤ 𝑗 ≤ 2} dan himpunan  sisi 𝐸(𝐺 𝑚,2 ) = {𝑤 𝑖,1 𝑤 𝑖,2 , 𝑤 𝑖,1 𝑤 𝑖+1,1 , 𝑤 𝑖,2 𝑤 𝑖+1,2 |1 ≤ 𝑖 ≤ 𝑚} .  Penentuan  batas  atas dimensi partisi pada graf 𝐺 𝑚,2 , diperoleh dengan mengkontruksi partisi pembeda ∏. Ambil partisi pembeda ∏ = {𝑆 1 , 𝑆 2 , 𝑆 3 } sedemikian sehingga: 𝑆 1 = {𝑤 1,1 } , 𝑆 2 = {𝑤 2,1 , 𝑤 3,1 , 𝑤 4,1 , … , 𝑤 𝑚,1 } dan 𝑆 3 = {𝑤 𝑖,2 |1 ≤ 𝑖 ≤ 𝑚, } .
Akan  ditunjukkan  bahwa  representasi  setiap  titik  di  graf 𝐺 𝑚,2 berbeda  terhadap ∏. dari  hasil observasi diperoleh representasi setiap titik di graf 𝐺 𝑚,2 sebagai berikut: 𝑟( 𝑤 1,1 | ∏ ) = (0,1,1) , 𝑟( 𝑤 𝑖,1 | ∏ ) = (𝑖 − 1,0,1) ; jika 2 ≤ 𝑖 ≤ 𝑚 , 𝑟( 𝑤 𝑖,2 | ∏ ) = (𝑖, 1,0) ; jika 2 ≤ 𝑗 ≤ 𝑛 .
Terlihat  dari  hasil  observasi  di  atas,  semua  titik  dari  graf 𝐺 𝑚,2 mempunyai  representasi yang berbeda. Jadi ∏ = {𝑆 1 , 𝑆 2 , 𝑆 3 } merupakan partisi pembeda dari graf 𝐺 𝑚,2 dengan kardinalitas ∏ adalah 3, sehingga diperoleh 𝑝𝑑(𝐺 𝑚,2 ) ≤ 3 . … (3.7)
Untuk batas bawah dimensi partisi graf 𝐺 𝑚,2 dapat dilakukan dengan cara yang sama pada proposisi  3.1  yang  menggunakan  Teorema  2.1(i),  sehingga  diperoleh  batas  bawah  pada  graf 𝐺 𝑚,2 adalah 𝑝𝑑(𝐺 𝑚,2 ) ≥ 3 .
… (3.8)
𝑤 1,4 𝑤 3,4 𝑤 2,4 Gambar 3.4. Graf 𝐺 3,4
𝑤 1,1 𝑤 1,2 𝑤 1,3 𝐺 3,4 : 𝑤 2,1 𝑤 3,1 𝑤 2,2 𝑤 3,2 𝑤 3,3 𝑤 2,3

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI

## Haspika, Hasmawati, Naimah Aris
Berdasarkan persamaan (3.7) dan (3.8) diperoleh batas atas dan batas bawah dimensi partisi graf 𝐺 yaitu 3 ≤ 𝑝𝑑(𝐺 𝑚,2 ) ≤ 3 . Jadi dimensi partisi dari graf 𝐺 𝑚,2 adalah 𝑝𝑑(𝐺 𝑚,2 ) = 3 . ∎
Dengan  cara  yang  serupa  dapat  ditunjukkan  bahwa 𝑝𝑑(𝐺 𝑚,𝑛 ) adalah  3  untuk 𝑚 = 4 dan 𝑛 = 4 , dan untuk 𝑚 ≥ 2 dan 𝑛 = 4 .
Teorema  3.1 Jika 𝑚, 𝑛  ≥ 2 dan 𝑛 bernilai  genap,  maka  dimensi  partisi  graf 𝐺 𝑚,𝑛 adalah 𝑝𝑑(𝐺 𝑚,𝑛 ) = 3 . Bukti:
Dari kontruksi graf grid diperoleh himpunan titik 𝑉(𝐺 𝑚,𝑛 ) = {𝑤 𝑖,𝑗 |1 ≤ 𝑖 ≤ 𝑚 𝑑𝑎𝑛 2 ≤ 𝑗 ≤ 𝑛} dan  himpunan  sisi 𝐸(𝐺 𝑚,𝑛 ) = {𝑤 𝑖,𝑗 𝑤 𝑖,𝑗+1 ; 𝑤 𝑖,𝑗 𝑤 𝑖+1,𝑗 |1 ≤ 𝑖 ≤ 𝑚 𝑑𝑎𝑛 1 ≤ 𝑗 ≤ 𝑚} .  Pembuktian Teorema menggunakan metode induksi matematika, yaitu:
1. Berdasarkan hasil dari Proposisi 3.1, sampai Proposisi 3.4 diproleh:
a) 𝑝𝑑(𝐺 2,2 ) = 3 ,
b) 𝑝𝑑(𝐺 3,2 ) = 3 ,
c) 𝑝𝑑(𝐺 3,4 ) = 3 ,
d) 𝑝𝑑(𝐺 4,4 ) = 3 ,
e) Untuk 𝑚 ≥ 2 , 𝑝𝑑(𝐺 𝑚,2 ) = 3 dan
f) Untuk 𝑚 ≥ 2 , 𝑝𝑑(𝐺 𝑚,4 ) = 3 .

## 2.a. Pada bagian ini yang diinduksi adalah 𝒏
Asumsikan  bahwa 𝑝𝑑(𝐺 𝑚,𝑛 ) = 3 adalah  benar  jika 𝑛 = 2𝑘 ,  yaitu 𝑝𝑑(𝐺 𝑚,2𝑘 ) = 3 untuk suatu 𝑚 ∈ {2,3,4,5, … . } dengan  partisi  pembeda  minimum  adalah ∏ = {𝑆 1 , 𝑆 2 , 𝑆 3 } 1 , 𝑆 1 = {𝑤 1,1 } , 𝑆 2 = {𝑤 2,1 , 𝑤 3,1 , 𝑤 4,1 , … , 𝑤 𝑚,1 } dan 𝑆 3 = {𝑤 𝑖,𝑗 |1 ≤ 𝑖 ≤ 𝑚, 2 ≤ 𝑗 ≤ 2𝑘} .
Selanjutnya  akan  ditunjukkan  bahwa  Teorema  juga  benar  untuk 𝑛 = 2(𝑘 + 1) ,    yaitu 𝑝𝑑(𝐺 𝑚,2(𝑘+1) ) = 3 untuk  suatu 𝑚 ∈ {2,3,4, … } .  Untuk  menentukan  dimesi  partisi  graf 𝐺 𝑚,2(𝑘+1) dapat  diperoleh  dengan  mengkontruksi  partisi  pembeda  graf 𝐺 𝑚,2(𝑘+1) .  Misalkan ∏ ′ 1 = {𝑆 1 ′ , 𝑆 2 ′ , 𝑆 3 ′ } sehingga demikian:
𝑆 1 ′ = {𝑤 1,1 } = 𝑆 1 , 𝑆 2 ′ = {𝑤 2,1 , 𝑤 3,1 , 𝑤 4,1 , … , 𝑤 𝑚,1 } = 𝑆 2 dan 𝑆 3 ′ = {𝑤 𝑖,𝑗 |1 ≤ 𝑖 ≤ 𝑚, 2 ≤ 𝑗 ≤ 2𝑘} ∪ {𝑤 𝑖,2(𝑘+1) | 2 ≤ 𝑖 ≤ 𝑚} = 𝑆 3 ∪ {𝑤 𝑖,2(𝑘+1) | 2 ≤ 𝑖 ≤ 𝑚} .
Representasi  seiap titik di graf 𝐺 𝑚,2(𝑘+1) terhadap ∏ ′ 1 adalah sebagai berikut: 𝑟( 𝑤 1,1 | ∏ ) 1 = (0,1,1) , 𝑟( 𝑤 1,𝑗 | ∏ ) 1 = (𝑗 − 1, 𝑗, 0) ; jika 2 ≤ 𝑗 ≤ 2𝑘 , 𝑟( 𝑤 𝑖,1 | ∏ ) 1 = (𝑖 − 1,0,1) ; jika 2 ≤ 𝑖 ≤ 𝑚 , 𝑟( 𝑤 𝑖,𝑗 | ∏ ) 1 = (𝑗 + 𝑖 − 2, 𝑗 − 1,0) ; jika 2 ≤ 𝑖 ≤ 𝑚, 2 ≤ 𝑗 ≤ 2𝑘 . 𝑟( 𝑤 1,2(𝑘+1) | ∏ ) ′ 1 = (2𝑘 + 1,2𝑘 + 2,0) ; 𝑟( 𝑤 𝑖,2(𝑘+1) | ∏ ) ′ 1 = (2𝑘 + 𝑖, 2𝑘 + 1,0) ; jika 2 ≤ 𝑖 ≤ 𝑚 .
Dapat  dilihat  dari  hasil  observasi  diatas  bahwa  representasi  setiap  titik 𝐺 𝑚,2(𝑘+1) terhadap ∏ ′ 1 adalah bebeda. Jadi 𝑝𝑑(𝐺 𝑚,𝑛 ) ≤ 3 , untuk setiap 𝑛 genap dan untuk suatu 𝑚 ≥ 2 .

## 2.b. Pada bagian ini yan diinduksi adalah 𝒎
Asumsikan bahwa 𝑝𝑑(𝐺 𝑚,𝑛 ) = 3 adalah benar jika 𝑚 = 𝑘 , yaitu 𝑝𝑑(𝐺 𝑘,𝑛 ) = 3 untuk suatu 𝑛 ∈ {2,4,6, … . } dengan partisi pembeda minimum adalah ∏ = {𝑆 1 , 𝑆 2 , 𝑆 3 } 2 , 𝑆 1 = {𝑤 1,1 } , 𝑆 2 = {𝑤 2,1 , 𝑤 3,1 , 𝑤 4,1 , … , 𝑤 𝑘,1 } dan 𝑆 3 = {𝑤 𝑖,𝑗 |1 ≤ 𝑖 ≤ 𝑘, 2 ≤ 𝑗 ≤ 𝑛 .

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI

## Haspika, Hasmawati, Naimah Aris
Selanjutnya  akan  ditunjukkan  bahwa  Teorema  juga  benar  untuk 𝑚 = 𝑘 + 1 ,  yaitu 𝑝𝑑(𝐺 𝑘+1,𝑛 ) = 3 untuk suatu 𝑛 ∈ {2,4,6, … } . Untuk menentukan dimesi partisi graf 𝐺 𝑘+1,𝑛 dapat diperoleh  dengan  mengkontruksi  partisi  pembeda  graf 𝐺 𝑘+1,𝑛 .  Misalkan ∏ = {𝑆 1 ′ , 𝑆 2 ′ , 𝑆 3 ′ } ′ 2
sehingga demikian:
𝑆 1 ′ = {𝑤 1,1 } = 𝑆 1 ,
𝑆 2 ′ = {𝑤 2,1 , 𝑤 3,1 , 𝑤 4,1 , … , 𝑤 𝑘,1 } ∪ {𝑤 𝑘+1,1 } = 𝑆 2 ∪ {𝑤 𝑘+1,1 } dan 𝑆 3 ′ = {𝑤 𝑖,𝑗 |1 ≤ 𝑖 ≤ 𝑘, 2 ≤ 𝑗 ≤ 𝑛} ∪ {𝑤 𝑘+1,𝑗 | 2 ≤ 𝑗 ≤ 𝑛} = 𝑆 3 ∪ {𝑤 𝑘+1,𝑗 | 2 ≤ 𝑗 ≤ 𝑛} .
Representasi setiap titik di graf 𝐺 𝑘+1,𝑛 terhadap ∏ ′ 2 adalah sebagai berikut:
𝑟( 𝑤 1,1 | ∏ ) = (0,1,1)
2 , 𝑟( 𝑤 1,𝑗 | ∏ ) 2 = (𝑗 − 1, 𝑗, 0) ; jika 2 ≤ 𝑗 ≤ 𝑛 , 𝑟( 𝑤 𝑖,1 | ∏ ) 2 = (𝑖 − 1,0,1) ; jika 2 ≤ 𝑖 ≤ 𝑘 , 𝑟( 𝑤 𝑖,𝑗 | ∏ ) 2 = (𝑗 + 𝑖 − 2, 𝑗 − 1,0) ; jika 2 ≤ 𝑖 ≤ 𝑘, 2 ≤ 𝑗 ≤ 𝑛 . 𝑟( 𝑤 𝑘+1,1 | ∏ ) ′ 2 = (𝑘, 0,1) ; 𝑟( 𝑤 𝑘+1,𝑗 | ∏ ) ′ 2 = (𝑗 + 𝑘 − 1, 𝑗 − 1,0) ; jika 2 ≤ 𝑗 ≤ 𝑛 .
Dapat  dilihat  dari  hasil  observasi  diatas  bahwa  representasi  setiap  titik 𝐺 𝑘+1,𝑛 terhadap ∏ ′ 2 adalah bebeda. Jadi 𝑝𝑑(𝐺 𝑚,𝑛 ) ≤ 3 , untuk setiap 𝑚 ≥ 2 dan untuk suatu 𝑛 bernilai genap.
Berdasarkan  2.a.  dan  2.b.  diperoleh  batas  atas  dimensi  partisi  dari  graf 𝐺 𝑚,𝑛 adalah 𝑝𝑑(𝐺 𝑚,𝑛 ) ≤ 3 ,  untuk  setiap 𝑚, 𝑛 ≥ 2 dan 𝑛 bernilai  genap,  selanjutnya  untuk  batas  bawah  dari dimensi  partisi  graf 𝐺 𝑚,𝑛 dapat  diperoleh  dengan  cara  yang  sama  dalam  penentuan  batas  bawah pada Proposisi 3.1 yaitu dengan merujuk pada Teorema 2.1(i) menyatakan bahwa 𝑝𝑑(𝐺) = 2 jika dan  hanya  jika 𝐺 = 𝑃 𝑛 ,  sehingga  diperoleh  batas  bawah  dimensi  partisi  graf 𝐺 𝑚,𝑛 adalah 𝑝𝑑(𝐺 𝑚,𝑛 ) ≥ 3 . Sehingga diperoleh batas atas dan batas bawah dimensi partisi graf 𝐺 𝑚,𝑛 adalah 3 ≤ 𝑝𝑑(𝐺 𝑚,𝑛 ) ≤ 3 .  Jadi  dimensi  partisi  dari  graf 𝐺 𝑚,𝑛 adalah 𝑝𝑑(𝐺 𝑚,𝑛 ) = 3 ,  untuk 𝑚, 𝑛 ≥ 2 dan 𝑛 bernilai genap. ∎

## Kesimpulan
Graf  grid  merupakan  graf  hasil  operasi  kali  antara  dua  graf  lintasan (𝑃 𝑚 × 𝑃 𝑛 ) .  Graf  grid dapat ditulis 𝐺 𝑚,𝑛 dengan orde 𝑚 × 𝑛 . Graf 𝐺 𝑚,𝑛 mempunyai himpunan titik 𝑉(𝐺 𝑚,𝑛 ) = {𝑤 𝑖,𝑗 |1 ≤ 𝑖 ≤ 𝑚, 1 ≤ 𝑗 ≤ 𝑛} dan himpunan sisi 𝐸(𝐺 𝑚,𝑛 ) = {𝑤 𝑖,𝑗 𝑤 𝑖,𝑗+1 ; 𝑤 𝑖,𝑗 𝑤 𝑖+1,𝑗 |1 ≤ 𝑖 ≤ 𝑚, 1 ≤ 𝑗 ≤ 𝑛} . Batas  bawah  dimensi  partisi  untuk  graf 𝐺 𝑚,𝑛 untuk  setiap 𝑚, 𝑛 ≥ 2 dan 𝑛 bernilai  genap adalah 𝑝𝑑(𝐺 𝑚,𝑛 ) ≥ 3 dan  batas  atasnya  adalah 𝑝𝑑(𝐺 𝑚,𝑛 ) ≤ 3 .  Karenanya  dimensi  partisi  untuk graf 𝐺 𝑚,𝑛 untuk setiap 𝑚, 𝑛 ≥ 2 dan 𝑛 bernilai genap berada diantara 3 ≤ 𝑝𝑑(𝐺 𝑚,𝑛 ) ≤ 3 sehingga diperoleh  dimensi  partisi  dari  graf 𝐺 𝑚,𝑛 untuk  setiap 𝑚, 𝑛 ≥ 2 dan 𝑛 bernilai  genap  adalah 𝑝𝑑(𝐺 𝑚,𝑛 ) = 3 .

## Daftar Puastaka
[1] Chartrand,  G.,  Salehi,  E.,  &  Zhang,  P.,  2000.  The  Partition  Dimension  of  a  Graph. Aequationes Math . No. 59, 45-54.
[2] Darmaji,  2011. Dimensi  Partisi  Graf  Multipartit  dan  Graf  Hasil  Korona  Dua  Graf Terhubung . Disertasi. Jurusan Matematika FMIPA ITB. Bandung.
[3] Dwi  Dayanti,  D.,  2018.  Infimum  Passing  Grade  Prodi  Pendidikan  Matematika  UNSIKA 2017. Sesiomadika , 187-195.

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI
Haspika, Hasmawati, Naimah Aris
[4] Grigorious,  C.,  Stephen,  S.,  Rajan,  B.,  Miller,  M.  &  William,  A.,  2014.  On  the  partition dimension  of  a  class  of  circulant  graphs. Information  Processing  Letters ,  Vol.  114,  No.  7, 353-356.
[5] Hasmawati, 2020. Pengantar dan Jenis-Jenis Graf . UPT Unhas Press, Makassar.
[6] Hasmawati,  Nurwahyu,  B.,  Syukur  Daming,  A.,  &  Kamal  Amir,  A.,  2021.  Dimensi  Partisi Graf  Kincir  Angin  Belanda. Jurnal  Matematika,  Statistika  dan  Komputasi ,  Vol.  17,  No.  3, 472-483.
[7] Hernando, C., Mora, M., Pelayo, I. M., Seara, C., cceres, J., & Puertas, M. L., 2005. On the metric dimension of some families of graphs. Eletronic Notes in Discrete mathematics . No. 22, 129-133.
[8] Ida  Bagus  Kade  Puja  Arimbawa,  K.,  &  Baskoro,  E.T.,  2015.  Partition  Dimension  of  Some Classes of Trees, Procedia Computer Science , 74, 67-72.
[9] Khuller,  S.,  dan  Raghavachari,  B.,  1996.  Landmark  in  Graph. Discrete  Appl . Math .  No.70, 217-229.
[10] Mehreen,  N.,  Farooq,  R.,  &  Akhter.  S.,  2018.  On  partition  dimension  of  fullerene graphs, AIMS Mathematics , Vol. 3, No. 3, 343-352.
[11] Moreno,  E.,  2020.  On  the  k-partition  Dimension  of  graphs. Theoretical  computer  science , 806, 42-52.
[12] Permana,  A.,  B,.  &  Darmaji,  2012.  Dimensi  Metrik  Graf  Pohon  Bentuk  Tertentu, Jurnal Teknik Pomits , Vol. 1, No. 1, 1- 4.
[13] Sudha,  S.,  &  Manikanda,  K.,  2015.  General  Pattern  of  Total  Coloring  of  a  Prims  Graph  of 𝑛 − Layers  and  a  Grid  Graph .  Internasional  Journal  of  Innovative  Science  and  Modern Engineering , Vol. 3, No. 03.
[14] Ur Rehman, T., & Mehreen,. N., 2020. Partition Dimension and Strong Metric Dimension of Chain Cycle, Jordan Journal of mathematics and statistics ,Vol. 13, No. 2, 305-325.
[15] Wijaya, K., 2010. Struktur Aljabar Ring . UPT Penerbitan Universitas Jember. Jember.