## DIMENSI METRIK GRAF HASIL OPERASI JEMBATAN DARI CATERPILLAR HOMOGEN DAN POT BUNGA DIPERUMUM
(Metric Dimension of Bridge Operation Graph from Caterpillar Homogen and Generalized Flower Pot Graphs)
Gusma Hidayanti, Amrullah* ) , Nani Kurniati, Laila Hayati Pendidikan Matematika, FKIP, Universitas Mataram, Jl. Majapahit No. 62 Mataram e-mail: hidayantigusma56@gmail.com, * ) amrullah@unram.ac.id * ) penulis korespondensi
Abstract. The  metric  dimension is  a  concept that  has  many  applications,  such  as robotic  navigation.  This  concept  will  distinguish  each  vertex  of a  graph  based  on some vertices. The distinguishing vertices are called the basis of the graph. Let 𝐺 be a connected graph, the metric dimension, 𝑑𝑖𝑚(𝐺) , is the smallest cardinality of the basis of graph 𝐺 . On this paper, we present the metric dimensions of the bridge graph of  a  homogeneous  caterpillar  graph 𝐶 𝑚,𝑛 and  a  generalized  flower  pot  graph 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 . This research was conducted by the approach of structure analysis by location of the bridge vertices, the edge of the bridge, and the order of the graph. The results  show  that  the  metric  dimensions  of  the  bridge  graph  are  at  least  can  be reduced at most 2 , and the maximum values are the same as the value of 𝑚(𝑛 − 1) + ∑ 𝑞 𝑖 𝑝 𝑖=1 − 2𝑝 .
Keywords: Metric dimension, caterpillar, unicyclic, bridge MSC2020: 05C12
Received: 02-03-2022, accepted: 18-03-2022

## 1. Pendahuluan
Penelitian dimensi graf telah banyak dilakukan dalam beberapa varians seperti dimensi partisi maupun dimensi metrik. Konsep dimensi tersebut telah digunakan dalam beberapa aplikasi.  Salah  satu  contoh  aplikasi  yang  menggunakan  dimensi  metrik  yaitu  navigasi robot  [1].  Dalam  hal  navigasi  robot,  pergerakan  robot  dapat  menggunakan  ruang  graf. Dalam  ruang  graf,  beberapa  simpul  diberikan  penanda  sehingga  simpul  dalam  graf terbedakan satu sama lain. Dengan kata lain, setiap simpul harus memiliki koordinat yang berbeda dan unik [2].
Kajian tentang dimensi metrik merupakan kajian yang menarik, dan pemanfaatan konsep banyak  digunakan  dalam  kehidupan  modern  saat  ini.  Dimensi  metrik  pada  teori  graf muncul pertama kali pada tahun 1976, yaitu pada jurnal ditulis oleh F. Harary dan R.A Milter  yang  berjudul  “ On  the  metrik  dimension  of  a  graph ”  [3].  Dimensi  metrik merupakan suatu konsep yang menggunakan himpunan pembeda.  Himpunan pembeda digunakan  dalam  penandaan  untuk  membedakan  semua  simpul  pada  graf.    Misalkan 𝐺(𝑉, 𝐸) adalah graf terhubung, 𝑊 ⊂  𝑉(𝐺) , dimensi metrik adalah kardinalitas minimum
dari himpunan pembeda 𝑊 yang dinotasikan dengan 𝑑𝑖𝑚(𝐺) [4–7].
Dimensi metrik graf caterpillar telah dipublikasikan oleh beberapa peneliti diantaranya Permana  [8]  dan  Wantika  [9].  Demikian  juga  dimensi  metrik  graf unicyclic telah dipubliksikan oleh banyak peneliti diantaranya Poisson dan Zhang [10] dan  Adawiyah [11].  Poisson  dam  Zhang  (2002)  [10]  menunjukkan  bahwa  jika 𝐺 = 𝑇 + 𝑒 adalah  graf unicyclic ,  dengan  graf  pohon 𝑇, maka 𝑑𝑖𝑚(𝑇) − 2 ≤ 𝑑𝑖𝑚(𝑇 + 𝑒) ≤ 𝑑𝑖𝑚(𝑇) + 1. Adapun graf 𝑇 yang akan digunakan dalam penelitian ini adalah graf pot bunga. Kajian dimensi  metrik  pada  kelas  graf  tertentu  telah  dikaji  oleh  beberapa  peneliti  diantaranya graf  petersen[12],  graf  bipartit  [13],  dan  graf  tangga  [14].  Bahkan  beberapa  penelitian menggunakan operasi graf seperti amalgamasi [15].
Salah  satu  operasi  yang  banyak  dikaji  dalam  teori  graf  adalah operasi jembatan yaitu operasi  yang  meghubungkan  dua  graf 𝐺 1 dan 𝐺 2 dengan  menambahkan  satu  sisi  baru, sebut 𝑒, sebagai  penghubung  dua  graf 𝐺 1 dan 𝐺 2 sehingga  diperoleh  graf  jembatan 𝐵(𝐺 1 , 𝐺 2 , 𝑒) [16]. Dimensi  graf  caterpilar maupun graf unicyclic telah dipublikasi oleh beberapa peneliti. Kajian pada operasi jembatan pada graf caterpillar dan unicyclic pot bunga belum ada yang mempublikasikan. Kajian ini akan menyajikan hubungan antara dimensi  metrik  graf  jembatan dim(𝐵(𝐺 1 , 𝐺 2 , 𝑒)) dengan  dimensi  metrik  graf  sebelum melalukan operasi jembatan 𝑑𝑖𝑚(𝐺 1 ) atau 𝑑𝑖𝑚(𝐺 2 ) .

## 2. Metodologi
Untuk  mendapatkan  hubungan  dimensi  metrik  graf  hasil  operasi  jembatan 𝑑𝑖𝑚(𝐵(𝐺 1 , 𝐺 2 , 𝑒)) dengan  dimensi  metrik  graf  sebelum  melalukan  operasi  jembatan 𝑑𝑖𝑚(𝐺 1 ) atau 𝑑𝑖𝑚(𝐺 2 ), dilakukan  pendekatan  menggunakan  analisis  struktur  graf dengan  memperhatikan  letak  simpul  dari  sisi  jembatan.  Berikut  definsi  graf  caterpillar yang digunakan.
Untuk setiap bilangan bulat 𝑚 ≥ 2 , graf caterpillar adalah graf pohon yang jika setiap simpul  berderajat  satu  dihapus  menghasilkan  graf  lintasan.  Jika  banyak  simpul  di  graf lintasan  adalah 𝑚 dan  selalu  ada 𝑛 simpul  yang  bertetangga  dengan  setiap  simpul  di lintasan, diperoleh graf caterpillar homogen, yang dinotasikan dengan 𝐶 𝑚,𝑛 . Lintasan 𝑃 𝑚 di 𝐶 𝑚,𝑛 disebut backbone dan  setiap simpul  yang berderajad satu  disebut daun . Semua daun  di 𝐶 𝑚,𝑛 diberi  label 𝑤 𝑖1 , 𝑤 𝑖2 , 𝑤 𝑖3 , . . . 𝑤 𝑖𝑛 untuk 𝑖 ∈ [1, 𝑚]. Sisi 𝑣 𝑖 𝑤 𝑖,𝑗 dengan 𝑗 ∈ [1, 𝑛] dan 𝑣 𝑖 𝑣 𝑖+1 berturut-turut disebut pandant dan sisi backbone [17]. Graf pot bunga , dinotasikan 𝐶 𝑘 − 𝑆 𝑛 , adalah  gabungan  graf  lingkaran 𝐶 𝑘 dan  graf  bintang 𝑆 𝑛 yang dihubungkan dengan sebuah sisi yang mengkaitkan titik pusat graf bintang  dengan salah satu  titik  pada  graf  lingkaran  [18].  Graf  pot  bunga  diperumum,  dinotasikan 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , adalah graf  yang diperoleh dari graf lingkaran 𝐶 𝑝 dengan menambahkan 𝑝
sisi yang menghubungkan  simpul pusat graf bintang 𝐾 𝑞 𝑖 dengan 1  ≤  𝑖  ≤ 𝑝 dan 𝑝 ≥  3 .
Kajian struktur dilakukan dengan memperhatikan setiap kemungkinan sisi jembatan 𝑢𝑣 dengan 𝑢 di  graf  caterpillar  dan 𝑣 di  graf  pot  bunga  diperumum.  Selanjutnya  analisis jarak  dan  representasi  simpul  dilakuka  dengan  menggunakan  sifat-sifat  yang  telah diperoleh pada kajian kajian sebelumnnya. Beberapa sifat  yang digunakan dalam kajian ini, diantaranya sebagai berikut:
Teorema  1. [8]  Jika 𝐶 𝑚,𝑛 dengan 𝑚 ≥ 1 𝑑𝑎𝑛 𝑛 ≥ 2 merupakan  graf  Caterpillar homogen maka 𝑑𝑖𝑚(𝐶 𝑚,𝑛 ) = 𝑚(𝑛 − 1) .
Teorema  2 .  [11]  Misalkan 𝐺 = 𝐶 𝑘 − 𝑆 𝑛 adalah  graf  pot  bunga  dengan 𝑘 ≥ 3, 𝑛 ≥ 2 , maka 𝑑𝑖𝑚 (𝐺) = 𝑛.
Teorema 3. [4] Graf terhubug 𝐺 dengan 𝑛 simpul mempunyai dimensi metrik 1 jika dan hanya jika 𝐺 = 𝑃 𝑛 .

## 3. Hasil dan Pembahasan
Misalkan himpunan titik dari graf 𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑥𝑦) dengan 𝑥 ∈ 𝑉(𝐶 𝑚,𝑛 ) dan 𝑦 ∈ 𝑉 (𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 ) adalah 𝑉 (𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑥𝑦)) = 𝑉(𝐶 𝑚,𝑛 ) ∪ 𝑉 (𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 ) dengan 𝑉(𝐶 𝑚,𝑛 ) = {𝑣 1 , 𝑣 2 , … , 𝑣 𝑚 } ∪ {𝑤 𝑗,𝑘 | 𝑗 ∈ [1, 𝑚], 𝑘 ∈ [1, 𝑛]} dan 𝑉 (𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 ) = {𝑎 1 , … , 𝑎 𝑝 } ∪ {𝑏 1,1 , … , 𝑏 1,𝑞 1 , 𝑏 2,1 , … , 𝑏 2,𝑞 2 , … , 𝑏 𝑝,1 , … , 𝑏 𝑝,𝑞 𝑝 } . Setelah dilakukan analisis dan kajian struktur dari kedua graf diperoleh lema-lema berikut.
Lema berikut memberikan dimensi graf jembatan 𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧) dengan sisi jembatan 𝑣 𝑚 𝑎 𝑖 atau 𝑣 𝑛 𝑏 1,𝑗 dengan 𝑣 𝑚 adalah simpul dari backbone di 𝐶 𝑚,𝑛 dan 𝑎 𝑖 atau 𝑏 1,𝑗 adalah bukan simpul daun di graf pot bunga.
Lemma 3.1 Misalkan 𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧) adalah graf hasil operasi jembatan graf caterpillar homogen 𝐶 𝑚,𝑛 dengan 𝑚, 𝑛 ≥ 2 dan  graf  pot  bunga  diperumum 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 dengan 𝑝 ≥ 3, 𝑞 𝑖 ≥ 2. Jika 𝑢𝑧 = 𝑣 𝑗 𝑎 𝑖 atau 𝑢𝑧 = 𝑣 𝑗 𝑏 𝑖,1 , ∀ 𝑖 ∈ {1, … , 𝑝}, 𝑗 ∈ {1,2, … , 𝑚} maka
𝑑𝑖𝑚 (𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) = 𝑚(𝑛 − 1) +   ∑(𝑞 𝑖 − 2).
𝑝 𝑖=1
Bukti .  Misalkan 𝑥 = 𝑣 𝑗 ∈ 𝑉(𝐶 𝑚,𝑛 ) dan 𝑦 = 𝑎 𝑖 ∈ 𝑉 (𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 ) atau 𝑦 = 𝑏 𝑖,1 ∈ 𝑉 (𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 ) untuk  suatu 𝑖 ∈ {1, … , 𝑝} .  Lema  ini  akan  dibuktikan  dalam  dua tahapan.
Pertama akan dibuktikan, 𝑑𝑖𝑚 (𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) ≤ 𝑚(𝑛 − 1) + ∑ (𝑞 𝑖 − 2). 𝑝 𝑖=1 Sebagai ilustrasi graf 𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧), perhatikan Gambar 3.1.
Gambar 1. Graf 𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑣 𝑚 𝑎 1 )
Dipilih  himpunan 𝑊 = {𝑤 11 , … , 𝑤 1(𝑛−1) ,   𝑤 21 , … , 𝑤 2(𝑛−1) , … ,   𝑤 (𝑚−1)1 , … , 𝑤 𝑚(𝑛−1) }
∪ {𝑏 12 , 𝑏 13 , … , 𝑏 1,𝑞 1 −1 } ∪ {𝑏 23 , … , 𝑏 2(𝑞 2 −1),…, 𝑏 𝑝2 , 𝑏 𝑝3 , … , 𝑏 𝑝,(𝑞 𝑟 −1) }. Untuk  setiap  simpul daun  di 𝐶 𝑚,𝑛 dipilih  menjadi  simpul  pembeda  keculai  simpul  daun 𝑤 𝑗,𝑛 dengan 𝑗 ∈ [1, 𝑚]. Oleh karena itu banyak simpul 𝑤 𝑗,𝑘 yang dipilih adalah 𝑚(𝑛 − 1) simpul.  Pada graf  pot  bunga,  untuk  setiap 𝑏 𝑖,𝑡 setiap  simpul  daun  dari 𝑏 𝑖,𝑡 dipilih  menjadi  simpul pembeda ( 𝑏 𝑖,2 , 𝑏 𝑖,3 , … , 𝑏 𝑖,𝑞 𝑖 −1 ) kecuali simpul daun 𝑏 𝑖,𝑞 𝑖 . Oleh karena itu banyak simpul 𝑏 𝑖,𝑡 yang dipilih adalah ∑ (𝑞 𝑖 − 2) 𝑝 𝑖=1 simpul.
Akan dibuktikan bahwa 𝑑𝑖𝑚 (𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) ≤ 𝑚(𝑛 − 1) +
∑ (𝑞 𝑖 − 1) 𝑝 𝑖=1 .  Ambil sembarang 𝑥, 𝑦 ∈ 𝑉 (𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) .
Untuk 𝑥, 𝑦 ∈ 𝐶 𝑚,𝑛 ,  jika 𝑥 = 𝑣 𝑖 dan 𝑦 = 𝑣 𝑗 dengan 𝑖 ≠ 𝑗 ∈   {1,2, … , 𝑚} ,  maka 𝑥 dan 𝑦 dibedakan  oleh 𝑤 𝑖𝑗 .  Jika 𝑥 = 𝑣 𝑖 dan 𝑦 = 𝑤 𝑗,𝑛 ,  maka 𝑥 dan 𝑦 dibedakan  oleh 𝑤 𝑖,𝑗 .  Jika 𝑥 = 𝑤 𝑖𝑛 dan 𝑦 = 𝑤 𝑗𝑛 dengan 𝑖 ≠ 𝑗 , maka 𝑥 dan 𝑦 dibedakan oleh 𝑤 𝑖𝑗 .
Untuk 𝑥, 𝑦 ∈ 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 jika 𝑥 = 𝑎 𝑖 dan 𝑦 = 𝑎 𝑗 dengan 𝑖 ≠ 𝑗 ∈   {1,2, … , 𝑝} maka maka 𝑥 dan 𝑦 dibedakan oleh 𝑏 𝑖𝑗 .
Untuk 𝑥 ∈ 𝐶 𝑚,𝑛 dan 𝑦 ∈ 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 Jika 𝑣 𝑗 dan 𝑎 𝑖 berjarak  sama  dengan 𝑏 𝑖,𝑡 maka dibedakan oleh 𝑤 𝑗.1 . Jika 𝑎 𝑖 dan 𝑤 𝑗,𝑛 berjarak sama dengan di 𝑤 𝑗,1 maka dibedakan oleh 𝑏 𝑖,𝑡 .
Selanjutnya menentukan kardinalitas dari 𝑊 . Karena untuk setiap 𝑣 𝑗 setiap simpul daun dari 𝑣 𝑗 dipilih menjadi simpul pembeda keculai simpul daun 𝑤 𝑗,𝑛 . Oleh karena itu banyak simpul 𝑤 𝑗,𝑘 yang dipilih adalah 𝑚(𝑛 − 1) simpul.  Pada graf pot bunga, Untuk setiap 𝑏 𝑖,𝑡 setiap simpul daun dari 𝑏 𝑖,𝑡 dipilih menjadi simpul pembeda ( 𝑏 𝑖,2 , 𝑏 𝑖,3 , … , 𝑏 𝑖,𝑞 𝑖 −1 ) kecuali simpul  daun 𝑏 𝑖,𝑞 𝑖 .  Oleh  karena  itu  banyak  simpul 𝑏 𝑖,𝑡 yang  dipilih  adalah ∑ (𝑞 𝑖 − 2) 𝑝 𝑖=1 simpul.  Akibatnya,  diperoleh |𝑊| = 𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 2) 𝑝 𝑖=1 .  Oleh  karena  itu, diperoleh
𝑑𝑖𝑚 (𝐵 (𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) ≤ 𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 2) 𝑝 𝑖=1 (1)
Kedua akan dibuktikan
𝑑𝑖𝑚 (𝐵 (𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) ≥ 𝑚(𝑛 − 1) +   ∑(𝑞 𝑖 − 2) 𝑝 𝑖=1
Misalkan dim (𝐵 (𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) =  𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 2) 𝑝 𝑖=1 − 1. Pada
pemilihan simpul-simpul daun dalam himpunan W, terdapat satu simpul daun ( 𝑤 𝑖,𝑛 atau 𝑏 𝑖,𝑞 𝑖 )    yang  tidak  dipilih.  Karena  pengandaian  tersebut,  terdapat  dua  simpul  daun  dari suatu 𝑣 𝑗 atau 𝑏 𝑖,𝑡 yang  tidak  dipilih  sebagai  simpul  pembeda.  Tanpa  mengurangi keumumannya  misalkan 𝑏 𝑖,2 dan 𝑏 𝑖,𝑞 𝑖 tidak  dipilih  sebagai  simpul  pembeda.  Karena 𝑏 𝑖,2 dan 𝑏 𝑖,𝑞 𝑖 berjarak sama ke setiap simpul 𝑧 ∈ 𝑉(𝐵) maka hal tersebut mengakibatkan 𝑟(𝑏 𝑖,2 |𝑊) = 𝑟(𝑏 𝑖,𝑞 𝑖 |𝑊) , kontradiksi. Hal serupa juga berlaku jika ada dua simpul daun 𝑤 𝑖,𝑗 yang tidak dipilih pada setiap 𝑣 𝑖 . Oleh karena itu, diperoleh
𝑑𝑖𝑚 (𝐵 (𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) ≥ 𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 2) 𝑝 𝑖=1 . (2)
Berdasarkan persamaan (1) dan (2), maka memperlihatkan
𝑑𝑖𝑚 (𝐵 (𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) = 𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 2) 𝑝 𝑖=1 . ▀
Pada  Lemma  3.2  berikut  ini  memperlihatkan  dimensi  metrik  dari  graf  jembatan
𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧) dengan  sisi  jembatan 𝑣 𝑗 𝑏 𝑖,𝑡 dimana 𝑣 𝑗 adalah  simpul backbone  dan 𝑏 𝑖,𝑡 dengan 𝑡 ≥  2 simpul  dari 𝐾 𝑖 ∗ .  Simpul 𝑏 𝑖,𝑡 dengan 𝑡 ≥  2 adalah simpul  daun  dari  graf  pot  bunga,  dimana 𝐾 𝑖 ∗ adalah  subgraf  dari  graf  pot  bunga 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 yang memuat pada simpul ke 𝑎 𝑖 dengan vertex {𝑎 𝑖 , 𝑏 𝑖1 , 𝑏 𝑖2 , 𝑏 𝑖3 , … , 𝑏 𝑖𝑞 𝑗 }.
Lemma 3.2 Misalkan 𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧) adalah graf hasil operasi jembatan graf caterpillar homogen 𝐶 𝑚,𝑛 dengan 𝑚, 𝑛 ≥ 2 dan  graf  pot  bunga  diperumum 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 dengan 𝑝 ≥ 3, 𝑞 𝑖 ≥ 2. Jika 𝑢𝑧 = 𝑣 𝑗 𝑏 𝑖,𝑡 ∀ 𝑖 ∈ {1, … , 𝑝} , 𝑗 ∈ {1,2, … 𝑚} , 𝑡 ∈ {2,3, . . , 𝑞 𝑖 } maka
𝑑𝑖𝑚 (𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) = 𝑚(𝑛 − 1) +   ∑(𝑞 𝑖 − 2) 𝑝 𝑖=1 − 1. Bukti. Misalkan 𝐺 1 = 𝐶 𝑚,𝑛 , 𝐺 2 =   𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝐵 (𝐺 1 , 𝐺 2 , 𝑢𝑧 ) dengan 𝑢  ∈ 𝑉(𝐺 1 ), 𝑧  ∈ 𝑉(𝐺 2 ), jika 𝑢 = 𝑣 𝑗 ∈   𝐺 1 , 𝑧 = 𝑏 𝑖,𝑡 ∈ V ( 𝐾 ∗ 𝑖 )  dengan i  ∈ {1, … , 𝑝}, 𝑡 ∈ {2,3, … , 𝑞 𝑗 } . Tanpa menggurangi keumumannya, 𝑏 𝑖,𝑡 = 𝑏 1,2 .  Lemma ini akan dibuktikan dalam 2 tahapan.
Pertama akan dibuktikan, 𝑑𝑖𝑚 (𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) ≤ 𝑚(𝑛 − 1) + ∑ (𝑞 𝑖 − 2) 𝑝 𝑖=1 − 1 .  Misalkan  sisi  jembatannya  adalah 𝑣 𝑗 𝑏 1,2 dengan 𝑏 1,2 adalah  simpul daun dari simpul 𝑏 1,1 dan 𝑗 ∈   {1,2, … , 𝑚} . Dipilih himpunan
𝑊 = {𝑤 1,1 , … , 𝑤 1,(𝑛−1) , 𝑤 2,1 , … , 𝑤 2,(𝑛−1) , … , 𝑤 (𝑚−1),1 , … , 𝑤 𝑚,(𝑛−1) } ∪ {𝑏 2,2 , 𝑏 2,3 , … , 𝑏 2,(𝑞−1),…, 𝑏 𝑝,2 , 𝑏 𝑝,3 , … , 𝑏 𝑝,(𝑞−1) } ∪ {𝑏 1,3 , … , 𝑏 1,(𝑞−1) } .
Pada  himpunan  W,  simpul  daun  yag  dipilih  dari  simpul 𝑏 1,1 adalah 𝑏 1,3 , … , 𝑏 1,(𝑞−1) dengan  simpul 𝑏 1,2 tidak  masuk  dalam  W,  sehingga  kardinalitas  W  berkurang  1  dari himpunan pembeda di Lemma 3.1 sebelumnya.
Akan dibuktikan bahwa 𝑑𝑖𝑚 (𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) ≤ 𝑚(𝑛 − 1) +
∑ (𝑞 𝑖 − 2) 𝑝 𝑖=1 − 1 . Ambil sembarang 𝑥, 𝑦 ∈ 𝑉 (𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) .  Untuk 𝑥, 𝑦 ∈ 𝐶 𝑚,𝑛 atau 𝑦 ∈ 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , pembuktian serupa dengan Lemma 3.1.
Untuk 𝑥, 𝑦 ∈ 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 .
Jika 𝑥 = 𝑎 𝑖 dan 𝑦 = 𝑎 𝑗 dengan 𝑖 ≠ 𝑗 ∈   {1,2, … , 𝑝} , maka maka 𝑥 dan 𝑦 dibedakan oleh simpul daun yang bertetangga dengan 𝑏 𝑖,1 . Jika 𝑥 = 𝑎 𝑖 dan 𝑦 = 𝑏 𝑗,𝑞 𝑖 dengan 𝑖 ≠ 𝑗 , maka maka 𝑥 dan 𝑦 dibedakan  oleh 𝑏 𝑖,𝑞 1 −1 .  Jika 𝑥 = 𝑏 𝑖,𝑞 𝑖 dan 𝑦 = 𝑏 𝑗,𝑞 𝑗 dengan 𝑖 ≠ 𝑗 ,  maka maka 𝑥 dan 𝑦 dibedakan oleh 𝑏 𝑖,𝑞 𝑖 −1 .
Oleh karena itu, hal tersebut menunjukkan bahwa W adalah himpunan pembeda dengan |𝑊| = 𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 2) 𝑝 𝑖=1 − 1 . Akibatnya, diperoleh
𝑑𝑖𝑚 (𝐵 (𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) ≤ 𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 2) 𝑝 𝑖=1 − 1. (3)
Kedua akan dibuktikan
𝑑𝑖𝑚 (𝐵 (𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) ≥ 𝑚(𝑛 − 1) +   ∑(𝑞 𝑖 − 2) 𝑝
𝑖=1 − 1.
Andaikan |𝑊| ≤ 𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 2) − 2 𝑝 𝑖=1 . Misalkan dim (𝐵 (𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) =  𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 2) − 2 𝑝 𝑖=1 . Karena  |W|= 𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 𝑝 𝑖=1
2) − 1 dengan  himpunan  W  memuat  setiap  simpul  daun 𝑤 𝑗,𝑘 dari 𝑣 𝑗 kecuali 𝑤 𝑗,𝑛 untuk setiap 𝑗 ∈   {1, … , 𝑚} .  Demikian  juga  setiap  simpul  daun 𝑏 𝑖,𝑠 dengan 𝑗 ∈   {1,2, … , 𝑝} , 𝑠 ∈ {1,2, … , 𝑞 𝑗 } kecuali 𝑏 𝑖,𝑞 𝑗 .  Dengan  pengandaian  tersebut,  maka  ada  dua  simpul  daun  dari suatu 𝑣 𝑗 atau 𝑏 𝑖,1 yang  bukan  merupakan  simpul  pembeda. Tanpa  mengurangi keumumannya misal 𝑏 𝑖3 dan 𝑏 𝑖5 . Karena 𝑏 𝑖3 dan 𝑏 𝑖5 berjarak sama ke setiap simpul 𝑣 ∈ 𝑉(𝐵) maka  hal  tersebut  mengakibatkan 𝑟(𝑏 𝑖3 |𝑊) = 𝑟(𝑏 𝑖5 |𝑊) .  Oleh  karena  itu, diperoleh
𝑑𝑖𝑚 (𝐵 (𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) ≥ 𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 2) − 1 𝑝 𝑖=1 . (4)
Berdasarkan pertidaksamaan (3) dan (4), maka diperoleh
𝑑𝑖𝑚 (𝐵 (𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) = 𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 2) − 1 𝑝 𝑖=1 .        ▀
Pada  Lemma  3.3  diperlihatkan  dimensi  metrik  dari  graf  jembatan 𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧) dengan  sisi  jembatan 𝑤 𝑗,𝑘 𝑏 𝑖,1 atau 𝑤 𝑗,𝑘 𝑎 𝑖 dengan 𝑤 𝑗,𝑘 adalah  simpul daun di 𝐶 𝑚,𝑛 , dan 𝑏 𝑖,1 atau 𝑎 𝑖 adalah simpul bukan daun dari graf pot bunga diperumum.
Lemma 3.3 Misalkan 𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧) adalah graf hasil operasi jembatan graf caterpillar homogen 𝐶 𝑚,𝑛 dengan 𝑚, 𝑛 ≥ 2 dan  graf  pot  bunga  diperumum 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 dengan 𝑝 ≥ 3, 𝑞 𝑖 ≥ 2. Jika 𝑢𝑧 = 𝑤 𝑗,𝑘 𝑎 𝑖 atau 𝑢𝑧 = 𝑤 𝑗,𝑘 𝑏 𝑖,1 , ∀ 𝑖 ∈ {1, … , 𝑝} , 𝑗 ∈ {1,2, … , 𝑚} , 𝑘 ∈ {1,2, … , 𝑛} maka
𝑑𝑖𝑚 (𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) = 𝑚(𝑛 − 1) +   ∑(𝑞 𝑖 − 2) − 1 𝑝 𝑖=1 .
Bukti. Misalkan 𝐺 1 = 𝐶 𝑚,𝑛 , 𝐺 2 =   𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝐺 = B(𝐺 1 , 𝐺 2 , 𝑢𝑧 )  dengan 𝑢  ∈ 𝑉(𝐺 1 ), 𝑧 ∈ 𝑉(𝐺 2 ) , j ika 𝑢 = 𝑣 𝑗 ∈   𝐺 1 , 𝑧  ∈ V ( 𝐾 ∗ 𝑖 )  untuk  suatu i  ∈ {1, … , 𝑝}. Lemma
ini akan dibuktikan dalam 2 tahapan.
Pertama akan dibuktikan, 𝑑𝑖𝑚(𝐺) ≤ 𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 2) − 1 𝑝 𝑖=1 .
Dipilih himpunan
𝑊 = {𝑤 11 , … , 𝑤 1(𝑛−1) , 𝑤 21 , … , 𝑤 2(𝑛−1) , … , 𝑤 (𝑚−1)1 , … , 𝑤 𝑚(𝑛−1) , 𝑏 12 , … , 𝑏 1(𝑞−1) } ∪
{𝑏 22 , 𝑏 23 , … , 𝑏 2(𝑞−1),…, 𝑏 𝑝2 , 𝑏 𝑝3 , … , 𝑏 𝑝(𝑞−1) } .
Akan dibuktikan bahwa W adalah himpunan pembeda dari 𝐺 . Ambil sembarang 𝑥, 𝑦 ∈ 𝑉(𝐺) .  Pembuktian ini, akan ditunjukkan pada 3 kasus berikut.
Kasus 1 . Untuk 𝑥, 𝑦 ∈ 𝐶 𝑚,𝑛 ⊂  𝐺 .
Jika 𝑑(𝑥, 𝑣) ≠  𝑑(𝑦, 𝑣) , maka simpul x dan y dibedakan oleh 𝑏 12 . Jika kedua simpul itu berjarak sama dengan simpul 𝑧 maka perhatikan pemilihan simpul 𝑥 dan 𝑦 . Jika 𝑥 = 𝑣 𝑗 dan 𝑦 = 𝑣 𝑡 dengan 𝑗 ≠ t ∈   {1,2, … , 𝑚} ,  maka 𝑥 dan 𝑦 dibedakan  oleh 𝑤 𝑗,𝑖 .  Jika 𝑥 = 𝑣 𝑗 dan 𝑦 = 𝑤 𝑡,𝑛 , maka 𝑥 dan 𝑦 dibedakan oleh 𝑤 𝑗,𝑖 . Jika 𝑥 = 𝑤 𝑗,𝑛 dan 𝑦 = 𝑤 𝑡.𝑛 dengan 𝑗 ≠ 𝑡 , maka 𝑥 dan 𝑦 dibedakan oleh 𝑤 𝑗.𝑖 .
Kasus 2 . Untuk 𝑥, 𝑦 ∈ 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑟 ⊂  𝐺.
Jika 𝑥 = 𝑎 𝑖 dan 𝑦 = 𝑎 𝑗 atau 𝑦 = 𝑏 𝑗,𝑖 dengan 𝑖 ≠ 𝑗 ∈   {1,2, … , 𝑝} ,  maka  maka 𝑥 dan 𝑦 dibedakan  oleh 𝑏 𝑖,2 .  Jika 𝑥 = 𝑎 𝑖 dan 𝑦 = 𝑏 𝑗,𝑖 dengan 𝑖 ≠ 𝑗 ,  maka  simpul 𝑥 dan 𝑦 dibedakan  oleh 𝑏 𝑗,2 .  Jika 𝑥 = 𝑏 𝑖𝑗 dan 𝑦 = 𝑏 𝑗𝑖 dengan 𝑖 ≠ 𝑗 ,  maka  simpul 𝑥 dan 𝑦 dibedakan oleh 𝑏 𝑖,2 .
Kasus 3 . Untuk 𝑥 ∈ 𝐶 𝑚,𝑛 dan 𝑦 ∈ 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 .
Karena 𝑑(𝑦, 𝑏 𝑖,2 ) ≤ 2 dan 𝑑(𝑥, 𝑏 𝑖,2 ) ≥ 3, 𝑖 ∈   {1,2, … , 𝑝} maka  kedua  simpul 𝑥 dan 𝑦 dibedakan oleh 𝑏 𝑖,2 .
Berdasarkan kasus 1, 2, dan 3 dapat disimpulkan bahwa W adalah himpunan pembeda dengan |𝑊| = 𝑚(𝑛 − 1) +  ∑ (𝑞 𝑖 − 2) − 1 𝑝 𝑖=1 . Oleh karena itu, diperoleh
𝑑𝑖𝑚 (𝐵( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝑟𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑟 , 𝑢𝑧)) ≤ 𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 2) − 1. 𝑝 𝑖=1 (5)
Kedua akan dibuktikan
𝑑𝑖𝑚 (𝐵( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝑟𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑟 , 𝑢𝑧)) ≥ 𝑚(𝑛 − 1) +   ∑(𝑞 𝑖 − 2) − 1 𝑝
𝑖=1 .
Andaikan |𝑊| = 𝑚(𝑛 − 1) +  ∑ (𝑞 𝑖 − 2) 𝑝 𝑖=1 , misalkan dim (𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) = |𝑊| ≤ 𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 2) 𝑝 𝑖=1 . Akibatnya terdapat paling
sedikit dua simpul daun dari suatu 𝑣 𝑗 atau 𝑎 𝑖 yang tidak dipilih sebagai simpul pembeda. Tanpa mengurangi keumumannya misalkan ada dua simpul daun dari suatu 𝑎 𝑖 yang tidak masuk sebagai simpul pembeda yaitu 𝑏 𝑖2 dan 𝑏 𝑖3 . Karena 𝑏 𝑖2 dan 𝑏 𝑖5 berjarak sama ke setiap simpul 𝑣 ∈ 𝑉(𝐵) maka hal tersebut mengakibatkan 𝑟(𝑏 𝑖2 |𝑊) = 𝑟(𝑏 𝑖3 |𝑊) .
Oleh karena itu, diperoleh
𝑑𝑖𝑚 (𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) ≥ 𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 2) 𝑝 𝑖=1 − 1. (6)
Berdasarkan persamaan (5) dan (6), maka diperoleh
𝑑𝑖𝑚 (𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) = 𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 2) 𝑝 𝑖=1 − 1 ▀
Lemma 3.4 Misalkan 𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧) adalah graf hasil operasi jembatan graf caterpillar homogen 𝐶 𝑚,𝑛 dengan 𝑚, 𝑛 ≥ 2 dan  graf  pot  bunga  diperumum 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 dengan 𝑝 ≥ 3, 𝑞 𝑖 ≥ 2. Jika 𝑢𝑧 = 𝑤 𝑗,𝑘 𝑏 𝑖,𝑡 , ∀ 𝑖 ∈ {1, … , 𝑝} , 𝑡 ∈   {2, … , 𝑞 𝑖 } , 𝑗 ∈ {1,2, … , 𝑚} , dan 𝑘 ∈ {1,2, … , 𝑛} maka
𝑑𝑖𝑚 (𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) = 𝑚(𝑛 − 1) +   ∑(𝑞 𝑖 − 2) 𝑝 𝑖=1 − 2.
Bukti. Misalkan 𝐺 1 = 𝐶 𝑚,𝑛 , 𝐺 2 =   𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , B (𝐺 1 , 𝐺 2 , 𝑢𝑧 )  dengan 𝑢  ∈ 𝑉(𝐺 1 ), 𝑧  ∈ 𝑉(𝐺 2 ) , dimana 𝑢 = 𝑤 𝑗,𝑘 ∈   𝐺 1 , 𝑧 = 𝑏 𝑖,𝑡 .  Tanpa  mengurangi  keumuman 𝑧 = 𝑏 1,2 .  Lemma ini akan dibuktikan dalam 2 tahapan.
Pertama akan dibuktikan, 𝑑𝑖𝑚 (𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) ≤ 𝑚(𝑛 − 1) +
∑ (𝑞 𝑖 − 2) 𝑝 𝑖=1 − 2. Sebagai  ilustrasi  graf 𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧), perhatikan Gambar 3.6.
Dipilih himpunan 𝑊 = {𝑤 11 , … , 𝑤 1(𝑛−1) , 𝑤 21 , … , 𝑤 2(𝑛−1) , … , 𝑤 𝑚1 , … , 𝑤 𝑚(𝑛−2) } ∪
{𝑏 13 , … , 𝑏 1(𝑞−1), } ∪ {𝑏 22 , 𝑏 23 , … , 𝑏 2(𝑞−1),…, 𝑏 𝑝2 , 𝑏 𝑝3 , … , 𝑏 𝑝(𝑞 𝑝 −1) }, dengan  |W|= 𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 2) 𝑝 𝑖=1 − 2. Ambil sembarang 𝑥, 𝑦 ∈ 𝑉 (𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 −
𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑤 𝑚,𝑛 𝑏 1,2 )) . Pembuktian ini,   akan ditunjukkan pada 3 kasus berikut.
Kasus 1 . Untuk 𝑥, 𝑦 ∈ 𝐶 𝑚,𝑛 .
Jika 𝑥 = 𝑣 𝑖 dan 𝑦 = 𝑣 𝑗 dengan 𝑖 ≠ 𝑗 ∈ {1,2, … , 𝑚} ,  maka 𝑥 dan 𝑦 dibedakan  oleh 𝑤 𝑖,𝑗 . Jika 𝑥 = 𝑣 𝑖 dan 𝑦 = 𝑤 𝑗,𝑛 , maka 𝑥 dan 𝑦 dibedakan oleh 𝑤 𝑖,𝑗 . Jika 𝑥 = 𝑤 𝑖,𝑛 dan 𝑦 = 𝑤 𝑗,𝑛 dengan 𝑖 ≠ 𝑗 , maka 𝑥 dan 𝑦 dibedakan oleh 𝑤 𝑖,𝑗 .
Gambar 2.  Graf 𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑤 𝑚𝑛 𝑏 12 )
Kasus 2 . Untuk 𝑥, 𝑦 ∈ 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 .
Jika 𝑥 = 𝑎 𝑖 dan 𝑦 = 𝑎 𝑗 dengan 𝑖 ≠ 𝑗 ∈   {1,2, … , 𝑝} , maka maka 𝑥 dan 𝑦 dibedakan oleh 𝑏 𝑖𝑗 .  Jika 𝑥 = 𝑎 𝑖 dan 𝑦 = 𝑏 𝑗𝑖 dengan 𝑖 ≠ 𝑗 ,  maka  maka 𝑥 dan 𝑦 dibedakan  oleh 𝑏 𝑖𝑗 .  Jika 𝑥 = 𝑏 𝑖𝑗 dan 𝑦 = 𝑏 𝑗𝑖 dengan 𝑖 ≠ 𝑗 , maka maka 𝑥 dan 𝑦 dibedakan oleh 𝑏 𝑖𝑗 .
Kasus 3 . Untuk 𝑥 ∈ 𝐶 𝑚,𝑛 dan 𝑦 ∈ 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 .
Misalkan 𝑦 = 𝑎 𝑖 atau 𝑦 = 𝑏 𝑖.𝑗 dengan 𝑗 ∈   {1,2, … , 𝑝} dan 𝑗 ∈   {1,2, … , 𝑞 𝑖 } ,  diperoleh 𝑑(𝑦, 𝑏 𝑖,𝑡 ) ≤ 2 dan 𝑑(𝑥, 𝑏 𝑖,𝑡 ) ≥ 3 untuk  suatu  simpul 𝑏 𝑖,𝑡 dengan 𝑡 ∈ {3,4, … , 𝑞 𝑖 } . Akibatnya  kedua simpul 𝑥 dan 𝑦 dibedakan oleh 𝑏 𝑖,𝑡 .
Berdasarkan kasus 1, 2, dan 3 dapat disimpulkan bahwa W adalah himpunan pembeda dengan |𝑊| = (𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 2) 𝑝 𝑖=1 − 2) . Oleh karena itu, diperoleh
𝑑𝑖𝑚 (𝐵( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝑟𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑟 , 𝑢𝑧)) ≤ (𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 2) 𝑝 𝑖=1 − 2). (7)
Kedua akan dibuktikan
𝑑𝑖𝑚 (𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) ≥ (𝑚(𝑛 − 1) +   ∑(𝑞 𝑖 − 2) 𝑝 𝑖=1 − 2). Andaikan
dim (𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) = 𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 2) 𝑝 𝑖=1 − 1.
Akibatnya  terdapat  dua  simpul  daun  dari  suatu 𝑣 𝑖 atau 𝑎 𝑖 yang  tidak  dipilih  sebagai simpul pembeda, tanpa mengurangi keumumannya misal 𝑏 𝑖3 dan 𝑏 𝑖4 . Karena 𝑏 𝑖3 dan 𝑏 𝑖4 berjarak sama ke setiap simpul 𝑣 ∈ 𝑉(𝐵) maka hal tersebut mengakibatkan 𝑟(𝑏 𝑖3 |𝑊) = 𝑟(𝑏 𝑖4 |𝑊) . Pembuktian ini kontradiksi, oleh karena itu diperoleh
𝑑𝑖𝑚 (𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) ≥ 𝑚(𝑛 − 1) +   ∑ (𝑞 𝑖 − 2) 𝑝 𝑖=1 − 2. (8)
Berdasarkan persamaan (7) dan (8), maka diperoleh
𝑑𝑖𝑚 (𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) = 𝑚(𝑛 − 1) +   ∑(𝑞 𝑖 − 2) 𝑝 𝑖=1 − 2. Berdasarkan Lemma 3.1 sampai Lemma 3.4 maka diperoleh Teorem 3.1 sebagai berikut.
Teorema  3.1 Misalkan 𝐶 𝑚,𝑛 adalah  caterpillar  homogen, 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 adalah  graf pot bunga diperumum  dan 𝐺 ∗ = (𝐵 ( 𝐶 𝑚,𝑛 , 𝐶 𝑝 − 𝐾 𝑞 1 , 𝑞 2 , … 𝑞 𝑝 , 𝑢𝑧)) . Jika dengan 𝑚, 𝑛 ≥ 2 dan 𝑝 ≥ 3, 𝑞 𝑖 ≥ 2 , 𝑖 ∈ {1,2, … , 𝑝} maka
𝑑𝑖𝑚(𝐺 ∗ ) = { 𝑆 jika  𝑢𝑧 = 𝑣 𝑗 𝑎 𝑖 atau 𝑢𝑧 = 𝑣 𝑗 𝑏 𝑖,1 , 𝑆 − 1 jika 𝑢𝑧 = 𝑣 𝑗 𝑏 𝑖,𝑡 atau 𝑢𝑧 = 𝑤 𝑗,𝑘 𝑎 𝑖 atau  𝑢𝑧 = 𝑤 𝑗,𝑘 𝑏 𝑖,1 , 𝑆 − 2 jika  𝑢𝑧 = 𝑤 𝑗,𝑘 .
dengan 𝑆 =  𝑚(𝑛 − 1) +   ∑ 𝑞 𝑖 𝑝 𝑖=1 − 2𝑝, 𝑗 ∈ {1,2, … , 𝑚}, 𝑘 ∈ {1,2, … , 𝑛} dan 𝑡 ∈ {2,3, … , 𝑞 𝑖 } .

## 4. Kesimpulan
Berdasarkan  hasil  utama  yang  diperoleh  dari  penelitian  ini,  dapat  disimpulan  bahwa bahwa dimensi metrik graf jembatan dari graf caterpillar homogen 𝐶(𝑚, 𝑛) dan pot bunga diperumum 𝐶 𝑝 − 𝐾 𝑞1 ,𝑞2 ,… 𝑞𝑝 adalah  paling  kecil  berkurang  dua  dari  nilai 𝑚(𝑛 − 1) + ∑ 𝑞 𝑖 𝑝 𝑖=1 − 2𝑝 .  Dimensi  metrik  terbesar  graf  jembatan  tersebut  adalah  sama  dengan 𝑚(𝑛 − 1) +   ∑ 𝑞 𝑖 𝑝 𝑖=1 − 2𝑝 .

## Daftar Pustaka
[1] Franz, M.O., Schölkopf,  B., Mallot, H.A., Bülthoff, H.H., (1998), Learning view graphs for robot navigation, Autonomous Robots 5 , 111-125.
[2] Khuller, S., Raghavachari, B., Rosenfeld, A., (1996), Landmark in graphs, Discrete Applied Mathematics 70(3) , 217-229. https://doi.org/10.1016/0166- 218X(95)00106-2
[3] Harary, F., Melter, R. A., (1976), On the metric dimension of a graph, Ars Comb 2 , 191-195.
[4] Chartrand, G., Eroh, L., Johnson, M. A., Oellermann, O. R., (2000), Resolvability in graphs and the metrik dimension of a graph, Discrete Applied Mathematics 105 , 99-113. https://doi.org/10.1016/S0166-218X(00)00198-0
[5] Chartrand, G., Salehi, E., Zhang, P., (2000), The partition dimension of a graph. Aequationes Mathematicae 59(1) , 45-54. https://doi.org/10.1007/PL00000127
[6] Sandika, K. G., (2015). Penentuan Banyaknya Graf Berlabel Tak Terhubung Tanpa Loop  Dengan  Lima  Titik, Skrpsi ,  Lampung:  Fakultas  Matematika  dan  Ilmu Pengetahuan Alam, Universitas Lampung.
[7] Sulistio,  W.,  Slamin,  S.,  (2017),  Analisis  dimensi  metrik  dengan  himpunan pembeda  terhubung  pada  graf  khusus  keluarga  pohon  dikaitkan  keterampilan berpikir tingkat tinggi, Kadikma 6(3) , 26-35.
[8] Permana,  A.  B.,  Darmaji.,  (2012),  Dimensi  metrik  graf  pohon  bentuk  tertentu, Jurnal  Tekhnik  Pomits 1 ,  1-4. http://digilib.its.ac.id/public/ITS-paper-24031- 1207100008-Paper.pdf
[9] Wantika,  R.R.,  (2016),  Dimensi  metrik  dan  diameter  dari  graf  ulat C m,n , Jurnal Buana Matematika 6(1) , 57-62.
[10] Poisson, C., Zhang, P., (2002), The metric dimension of unicyclic graphs, Journal of Combinatorial Mathematics and Combinatorial Computing 40 , 17-32.
[11] Estrada-Moreno,  A.,  (2021),  The k -metric  dimension  of  a  unicyclic  graph, Mathematics 9(21) , 2789. https://doi.org/10.3390/math9212789
[12] Asmiati, A., Aldino, A. A., Notiragayu, N., Zakaria, L., Muslim Ansori, M., (2019), Dimensi  metrik  hasil  operasi  tertentu  pada  graf  petersen  diperumum. Limits:
Journal of Mathematics and Its Applications 16(2) , 87-93.
http://dx.doi.org/10.12962/limits.v16i2.5594
[13] Bača, M., Baskoro, E. T., Salman, A. N. M., Saputro, S. W., Suprijanto, D., (2011), The  metric  dimension  of  regular  bipartite  graphs, Bulletin  mathématique  de  la Société des Sciences Mathématiques de Roumanie 54(1) , 15-28.
[14] Angraini, F., Welyyanti, D., (2018), Dimensi metrik dan dimensi partisi dari graf tangga  segitiga Tr n untuk n =  2;  3, Jurnal  Matematika  UNAND 7(2) ,  46-52. https://doi.org/10. 25077/jmu.7.2.46-52.2018
[15] Febrianti,  F.,  Yulianti,  L.,  Narwen,  N.,  (2019),  Dimensi  metrik  pada  graf amalgamasi  tangga  segitiga  diperumum  homogen, Jurnal  Matematika  UNAND 8(1) , 84-90. https://doi.org/10. 25077/jmu.8.1.84-90.2019
[16] Amrullah,  A.,  Syahrul,  A.,  Turmuzi,  M.,  Nani,  K.,  (2021),  The  bridge  graphs partition  dimension, In  Journal  of  Physics:  Conference  Series , IOP  Publishing 1779(1) , 012086. DOI: 10.1088/1742-6596/1779/1/012086
[17] Amrullah,  Assiyatun,  H.,  Baskoro,  E.  T.,  Uttunggadewa,  S.,  Simanjuntak,  R., (2013),  The  partition  dimension  for  a  subdevision  of  homogeneous  caterpillars, AKCE Int. J. Graph Comb , 317-325.
[18] Ahmad, M., (2012), Pelabelan Graceful dan Pelabelan ρ Pada Graf Pot Bunga dan Graf  Pohon  Palem, Tesis ,  Depok:  Fakultas  Matematika  dan  Ilmu  Pengetahuan Alam, Universitas Indonesia.