## Contemporary Mathematics and Applications
Vol. 1, No. 1, 2019, pp. 1-18.

## Dimensi Metrik Ketetanggaan Lokal Graf Hasil
Operasi 𝒌 -Comb
Fryda Arum Pratama 1 , Liliek Susilowati 2,* , Moh. Imam Utoyo 3
1,2,3 Departemen Matematika, Fakultas Sains dan Teknologi, Kampus C Universitas Airlangga, Jl. Mulyorejo, Surabaya
*Corresponding author: liliek-s@fst.unair.ac.id
Abstract - Research on the local adjacency metric dimension has not been found in all operations of the graph, one of them is comb product graph. The purpose of this research was to determine the local adjacency metric dimension of k-comb product graph and level k comb product graph between any connected graph G and H . In this research graph G and graph H such as cycle graph, complete graph, path graph, and star graph. K-comb product graph between any graph G and H denoted by G𝐨 𝐤 H . While level k comb product graph between any graph G and H denoted by G𝐨 𝐤 H .
In this research, local adjacency metric dimension of G𝐨 𝐤 S m graph only dependent to multiplication of the cardinality of V(G) and many of k value, while G𝐨 𝐤 K m graph and G𝐨 𝐤 C m graph is dependent to dominating number of G and multiplication of the cardinality of V(G) , many of k value, and local adjacency metric dimension of K m graph or C m graph. And then, local adjacency metric dimension of G𝐨 𝐤 S m graph only dependent to the cardinality of V(G𝐨 k−1 S m ) , while G𝐨 𝐤 K m graph and G𝐨 𝐤 C m graph  is  dependent  to  dominating  number  of G and  multiplication  of  the  local  adjacency  metric dimension of K m graph or C m graph with cardinality of V(G𝐨 k−1 K m ) or V(G𝐨 k−1 C m ) .
Keywords: Local Adjacency Metric Dimension,  k-Comb Product Graph, Level k Comb Product Graph, Complete Graph, Path Graph, Cycle Graph, and Star Graph.

## 1 Pendahuluan
Teori graf merupakan salah satu cabang ilmu matematika yang dapat digunakan sebagai penyelesaian masalah apabila permasalah tersebut disajikan dalam bentuk titik ( vertex ) dan sisi ( edge ). Salah satu kajian yang terus berkembang dalam teori graf adalah dimensi metrik. Konsep dimensi metrik dikenalkan oleh Frank Harary pada tahun 1976. Penelitian dimensi  metrik  dilakukan  salah  satunya  oleh  Iswadi  dkk  [1]  pada  graf  hasil  operasi korona.  Pada  tahun  2010,  Okamoto  dkk  [2]  memodifikasi  himpunan  pembeda  pada dimensi  metrik  menjadi  himpunan  pembeda  lokal.  Himpunan  pembeda  pada  dimensi metrik  juga  dimodifikasi  oleh  Jannesari  dan  Omoomi  [3]  menjadi  himpunan  pembeda ketetanggaan. Selanjutnya, Rodriguez dkk [4] memunculkan definisi himpunan pembeda ketetanggaan  lokal  dengan  menggabungkan  definisi  himpunan  pembeda  lokal  dan himpunan pembeda ketetanggaan.
Penelitian  dilanjutkan  oleh  Rodriguez  dan  Fernau  [5]  meneliti  dimensi  metrik ketetanggaan dan dimensi metrik ketetanggaan lokal pada graf operasi korona dan graf hasil kali kuat . Pada penelitian tersebut juga dijelaskan dimensi metrik ketetanggaan lokal dari graf bintang, graf lintasan, graf siklus, dan graf lengkap. Selanjutnya pada tahun yang sama  penelitian  dilanjutkan  oleh  Susilowati,  dkk  [6]  tentang  kekomutatifan  operasi korona dan graf hasil operasi kali comb secara dimensi metrik dan secara dimensi metrik lokal. Dalam  penelitian tersebut  diperkenalkan definisi operasi k- comb  untuk  sebarang graf 𝐺 dan 𝐻 . Selain itu, dijelaskan pula dimensi metrik dan dimensi metrik lokal dari graf  operasi k- comb.  Pada  penelitian  ini  dimensi  metrik  ketetanggaan  lokal dikembangkan pada graf operasi comb, comb tingkat k dan k- comb yaitu.
Menurut  Rodriguez  dan  Fernau  [5],  misalkan 𝐺 graf  terhubung,  himpunan  titik  yang bertetangga dengan titik 𝑣 pada graf 𝐺 dinotasikan sebagai 𝑁(𝑣) . Himpunan 𝑊 adalah himpunan pembeda ketetanggan lokal ( local adjacency resolving set ) jika untuk setiap dua  titik  yang  bertetangga 𝑥, 𝑦 ∈ 𝑉(𝐺) −  𝑊 terdapat 𝑧 ∈ 𝑊 sedemikian  hingga |𝑁(𝑧) ∩ {𝑥, 𝑦}| = 1 .  Himpunan  pembeda  ketetanggan  lokal  dengan  kardinalitas minimum  disebut  basis  ketetanggan  lokal  ( local  adjacency  basis )  untuk  graf 𝐺 , sedangkan  kardinalitas  dari  basis  disebut  dimensi  metrik  ketetanggan  lokal  yang dinotasikan dengan 𝑑𝑖𝑚 𝐴𝑙 (𝐺) .

## 2 Dimensi Metrik Ketetanggaan Lokal Graf Hasil Operasi 𝒌 − Comb
Berikut  ini  disajikan  sifat  himpunan  pembeda  ketetanggaan  local  pada  graf  siklus  dan graf lintasan.
Lema 2.1 Misalkan 𝐺 merupakan graf 𝑃 𝑛 atau graf 𝐶 𝑛 , 𝑊′ ⊆ 𝑉(𝐺) , dan 𝑊′ = {𝑣 𝑛 𝑖 |𝑖 = 1,2, … , 𝑘 dengan 𝑛 𝑖 < 𝑛 𝑖+1 } .  Jika  terdapat 𝑣 𝑛 𝑖 , 𝑣 𝑛 𝑖+1 ∈ 𝑊′ sehingga 𝑙(𝑣 𝑛 𝑗 − 𝑣 𝑛 𝑗+1 ) > 4 maka 𝑊′ bukan himpunan pembeda ketetanggaan lokal.
Bukti . Misalkan 𝐺 merupakan graf 𝑃 𝑛 atau graf 𝐶 𝑛 dengan 𝑉(𝐺) = {𝑣 1 , 𝑣 2 , … , 𝑣 𝑛 } , 𝑊′ ⊆ 𝑉(𝐺) dan 𝑊′ = {𝑣 𝑛 𝑖 |𝑖 = 1,2, … , 𝑘 dengan 𝑛 𝑖 < 𝑛 𝑖+1 } .  Jika  terdapat 𝑣 𝑛 𝑖 , 𝑣 𝑛 𝑖+1 ∈ 𝑊′ dengan 𝑙(𝑣 𝑛 𝑖 − 𝑣 𝑛 𝑖+1 ) > 4 ,  berdasarkan  himpunan  titik  pada  graf 𝐺 diperoleh  bahwa 𝑣 (𝑛 𝑖 )+𝑗 ∈ 𝑉(𝐺) − 𝑊′ dengan 𝑗 ∈ {1,2, … , 𝑡}, 𝑡 ≥ 5 sehingga  terdapat 𝑣 (𝑛 𝑖 )+2 , 𝑣 (𝑛 𝑖 )+3 ∈ 𝑉(𝐺) − 𝑊′ .
Untuk 𝐺 merupakan graf 𝑃 𝑛 . Diambil sebarang 𝑣 ∈ 𝑊′ maka terdapat tiga kemungkinan yaitu:
(i) Jika 𝑣 = 𝑣 𝑛 𝑖 ,  maka 𝑁(𝑣) = { {𝑣 (𝑛 𝑖 )+1 }, untuk 𝑛 𝑖 = 1 {𝑣 (𝑛 𝑖 )+1 , 𝑣 (𝑛 𝑖 )−1 }, untuk 𝑛 𝑖 yang lain sehingga |{𝑣 (𝑛 𝑖 )+2 , 𝑣 (𝑛 𝑖 )+3 } ∩ 𝑁(𝑣)| = 0 ≠ 1
(ii) Jika 𝑣 = 𝑣 𝑛 𝑖+1 , maka 𝑁(𝑣) = { {𝑣 (𝑛 𝑖+1 )−1 }, untuk 𝑛 𝑖+1 = 𝑛 {𝑣 (𝑛 𝑖+1 )+1 , 𝑣 (𝑛 𝑖+1 )−1 }, untuk  𝑛 𝑖+1 yang lain sehingga |{𝑣 (𝑛 𝑖 )+2 , 𝑣 (𝑛 𝑖 )+3 } ∩ 𝑁(𝑣)| = 0 ≠ 1
(iii) Jika 𝑣 ≠ 𝑣 𝑛 𝑖 dan 𝑣 ≠ 𝑣 𝑛 𝑖+1 maka terdapat 𝑛 𝑘 < 𝑛 𝑖 sehingga 𝑣 = 𝑣 𝑛 𝑘 atau terdapat 𝑛 𝑡 > 𝑛 𝑖+1 sehingga 𝑣 = 𝑣 𝑛 𝑡 .  Oleh  karena  itu, 𝑣 (𝑛 𝑖 )+2 , 𝑣 (𝑛 𝑖 )+3 ∉ 𝑁(𝑣) sehingga |{𝑣 (𝑛 𝑖 )+2 , 𝑣 (𝑛 𝑖 )+3 } ∩ 𝑁(𝑣)| = 0 ≠ 1 .
Untuk 𝐺 merupakan graf 𝐶 𝑛 . Diambil sebarang 𝑧 ∈ 𝑊′ maka terdapat tiga kemungkinan yaitu:
(i) Jika 𝑧 = 𝑣 𝑛 𝑖 , maka 𝑁(𝑧) = { {𝑣 (𝑛 𝑖 )+1 , 𝑣 𝑛 }, untuk 𝑛 𝑖 = 1 {𝑣 (𝑛 𝑖 )+1 , 𝑣 (𝑛 𝑖 )−1 }, untuk 𝑛 𝑖 yang lain sehingga |{𝑣 (𝑛 𝑖 )+2 , 𝑣 (𝑛 𝑖 )+3 } ∩ 𝑁(𝑧)| = 0 ≠ 1
(ii) Jika 𝑧 = 𝑣 𝑛 𝑖+1 , maka 𝑁(𝑧) = { {𝑣 1 , 𝑣 (𝑛 𝑖+1 )−1 }, untuk 𝑛 𝑖+1 = 𝑛 {𝑣 (𝑛 𝑖+1 )+1 , 𝑣 (𝑛 𝑖+1 )−1 }, untuk 𝑛 𝑖+1 yang lain sehingga |{𝑣 (𝑛 𝑖 )+2 , 𝑣 (𝑛 𝑖 )+3 } ∩ 𝑁(𝑧)| = 0 ≠ 1
(iii) Jika 𝑧 ≠ 𝑣 𝑛 𝑖 dan 𝑧 ≠ 𝑣 𝑛 𝑖+1 maka terdapat 𝑛 𝑘 < 𝑛 𝑖 sehingga 𝑧 = 𝑣 𝑛 𝑘 atau terdapat 𝑛 𝑡 > 𝑛 𝑖+1 sehingga 𝑧 = 𝑣 𝑛 𝑡 .  Oleh  karena  itu, 𝑣 (𝑛 𝑖 )+2 , 𝑣 (𝑛 𝑖 )+3 ∉ 𝑁(𝑧) sehingga |{𝑣 (𝑛 𝑖 )+2 , 𝑣 (𝑛 𝑖 )+3 } ∩ 𝑁(𝑧)| = 0 ≠ 1 .
Berdasarkan  uraian  di  atas  diperoleh  bahwa 𝑊′ bukan  merupakan  himpunan  pembeda ketetanggaan lokal. ∎
Pada penelitian ini dilengkapi pula hasil dimensi metrik ketetanggaan local dari graf 𝐶 𝑛 , graf 𝑃 𝑛 , graf 𝐾 𝑛 , dan graf 𝑆 𝑛 yang sudah ditemukan oleh Rodriquez, hanya saja disajikan kembali  dilengkapi  dengan  bukti  analitiknya  yang  belum  dijelaskan  pada  penelitian sebelumnya.
Teorema 2.2 [4]. 𝑑𝑖𝑚 𝐴𝑙 (𝑃 𝑛 ) = ⌈ 𝑛−1 4 ⌉ dengan 𝑛 ≥ 2 .
Bukti. Misalkan 𝑉(𝑃 𝑛 ) = {𝑣 𝑖 |𝑖 = 1,2, … , 𝑛} dan 𝐸(𝑃 𝑛 ) = {(𝑣 𝑖 , 𝑣 𝑖+1 )|𝑖 = 1,2, … , 𝑛 − 1} . Terdapat  lima  kemungkinan  nilai 𝑛 pada  graf 𝑃 𝑛 yaitu 𝑛 = 2 atau  terdapat 𝑚 ≥ 1 sehingga 𝑛 = 4𝑚 − 1, 𝑛 = 4𝑚, 𝑛 = 4𝑚 + 1, atau 𝑛 = 4𝑚 + 2 .
i. Jika 𝑛 = 2 , dipilih 𝑊 = {𝑣 2 } . Karena tidak terdapat pasangan titik yang bertetangga 𝑥, 𝑦 ∈ 𝑉(𝑃 𝑛 ) − 𝑊 ,  maka 𝑊 merupakan  himpunan  pembeda  ketetanggaan  lokal dengan |𝑊| = ⌈ 2−1 4 ⌉ .
ii. Jika 𝑛 = (4𝑚 + 2), 𝑚 ∈ ℕ .  Misalkan 𝑊 = {𝑣 3+4(𝑘−1) : 𝑘 < ⌈ 𝑛−1 4 ⌉ , 𝑘 ∈ ℕ} ∪ {𝑣 𝑛 } sehingga |𝑊| = ⌈ 𝑛−1 4 ⌉ . Diambil sebarang 𝑣 𝑖 ∈ 𝑊 pada graf 𝑃 𝑛 maka 𝑣 𝑖 = 𝑣 3+4(𝑘−1) dengan 𝑘 < ⌈ 𝑛−1 4 ⌉ , 𝑘 ∈ ℕ atau 𝑣 𝑖 = 𝑣 𝑛 , sehingga
𝑁(𝑣 𝑖 ) =   { {𝑣 𝑛−1 }, untuk 𝑣 𝑖 = 𝑣 𝑛 {𝑣 3+4(𝑘−1)+1 , 𝑣 3+4(𝑘−1)−1 }, untuk 𝑣 𝑖 = 𝑣 3+4(𝑘−1) Diambil sebarang titik bertetangga 𝑥, 𝑦 ∈ 𝑉(𝑃 𝑛 ) − 𝑊 , terdapat dua kemungkinan titik bertetangga  yaitu 𝑥 = 𝑣 3+4(𝑘−1)−2 , 𝑦 = 𝑣 3+4(𝑘−1)−1 dan 𝑥 = 𝑣 3+4(𝑘−1)+1 , 𝑦 = 𝑣 3+4(𝑘−1)+2 dengan 𝑘 < ⌈ 𝑛−1 4 ⌉ , 𝑘 ∈ ℕ . Oleh karena itu,
|{𝑣 3+4(𝑘−1)−2 , 𝑣 3+4(𝑘−1)−1 }⋂𝑁(𝑣 3+4(𝑘−1) )| = |{𝑣 3+4(𝑘−1)−1 }| = 1 atau |{𝑣 3+4(𝑘−1)+1 , 𝑣 3+4(𝑘−1)+2 }⋂𝑁(𝑣 3+4(𝑘−1) )| = |{𝑣 3+4(𝑘−1)+1 }| = 1 . Berdasarkan uraian  di  atas  dapat  disimpulkan  bahwa 𝑊 merupakan  himpunan  pembeda ketetanggaan lokal dengan |𝑊| = ⌈ 𝑛−1 4 ⌉ . iii. Sedangkan jika 𝑛 = 4𝑚 − 1, 𝑛 = 4𝑚, atau 𝑛 = 4𝑚 + 1 . Misalkan 𝑊 =
{𝑣 3 , 𝑣 7 , … , 𝑣 3+4(𝑘−1) , … , 𝑣 [3+4(⌈ 𝑛−1 4 ⌉−1)] } dengan 𝑘 merupakan urutan titik ke- 𝑘 pada 𝑊 dengan 𝑘 = 1,2,3, … , ⌈ 𝑛−1 4 ⌉ sehingga |𝑊| = ⌈ 𝑛−1 4 ⌉ . Diambil sebarang 𝑣 𝑖 ∈ 𝑊 pada graf 𝑃 𝑛 maka  terdapat 𝑖 = 3, 7, … , 3 + 4(𝑘 − 1), … , 3 + 4 (⌈ 𝑛−1 4 ⌉ − 1) sehingga diperoleh
𝑁(𝑣 𝑖 ) =   { {𝑣 𝑛−1 }, untuk 𝑣 𝑖 = 𝑣 𝑛 {𝑣 3+4(𝑘−1)+1 , 𝑣 3+4(𝑘−1)−1 }, untuk yang lain
Diambil  sebarang  titik  yang  bertetangga 𝑥, 𝑦 ∈ 𝑉(𝑃 𝑛 ) − 𝑊 ,  maka  terdapat  dua kemungkinan dua titik bertetangga yaitu 𝑥 = 𝑣 3+4(𝑘−1)−2 , 𝑦 = 𝑣 3+4(𝑘−1)−1 dan 𝑥 = 𝑣 3+4(𝑘−1)+1 , 𝑦 = 𝑣 3+4(𝑘−1)+2 dengan 𝑘 = 1,2, … , ⌈ 𝑛−1 4 ⌉ . Oleh karena itu: |{𝑣 3+4(𝑘−1)−2 , 𝑣 3+4(𝑘−1)−1 } ∩ 𝑁(𝑣 3+4(𝑘−1) )| = |{𝑣 3+4(𝑘−1)−1 }| = 1 atau |{𝑣 3+4(𝑘−1)+1 , 𝑣 3+4(𝑘−1)+2 } ∩ 𝑁(𝑣 3+4(𝑘−1) )| = |{𝑣 3+4(𝑘−1)+1 }| = 1 .
Berdasarkan  uraian  di  atas 𝑊 merupakan  himpunan  pembeda  ketetanggaan  lokal. Selanjutnya  ditunjukkan  bahwa 𝑊 merupakan  basis  ketetanggaan  lokal  pada  graf lintasan. Diambil sebarang 𝑈 ⊆ 𝑉(𝑃 𝑛 ) dengan |𝑈| < |𝑊| . Terdapat tiga kasus yaitu 𝑛 ≤ 5 , 5 < 𝑛 ≤ 9 , atau 𝑛 > 9 .
(i) Untuk 𝑛 ≤ 5 , |𝑈| < |𝑊| = ⌈ 𝑛−1 4 ⌉ = 1 akibatnya 𝑈 = ∅ .  Berdasarkan  Definisi himpunan  pembeda  ketetanggaan  lokal  maka 𝑈 bukan  merupakan  himpunan pembeda ketetanggaan lokal.
(ii) Untuk 5 < 𝑛 ≤ 9 , |𝑈| < |𝑊| = ⌈ 𝑛−1 4 ⌉ = 2 akibatnya |𝑈| = 1 . Misalkan 𝑈 = {𝑣 𝑖 } . Karena |𝑉(𝑃 𝑛 ) − 𝑈| ≥ 5 maka  terdapat  pasangan  titik  bertetanga 𝑣 𝑗 , 𝑣 𝑗+1 ∈ 𝑉(𝑃 𝑛 ) − 𝑈 dengan 𝑑(𝑣 𝑖 , 𝑣 𝑗 ) > 1 atau 𝑑(𝑣 𝑖 , 𝑣 𝑗+1 ) > 1 sehingga |{𝑣 𝑗 , 𝑣 𝑗+1 } ∩ 𝑁(𝑣 𝑖 )| = 0 ≠ 1 .  Berdasarkan  Definisi  himpunan  pembeda  ketetanggaan  lokal maka 𝑈 bukan merupakan himpunan pembeda ketetanggaan lokal.
(iii) Untuk 𝑛 > 9 , terdapat dua kemungkinan jarak antara anggota 𝑈 yaitu untuk setiap 𝑣 𝑖 , 𝑣 𝑗 ∈ 𝑈 dengan 𝑖 < 𝑗 , 𝑑(𝑣 𝑖 , 𝑣 𝑗 ) < 5 atau  terdapat 𝑣 𝑖 , 𝑣 𝑗 ∈ 𝑈 dengan 𝑖 < 𝑗, 𝑑(𝑣 𝑖 , 𝑣 𝑗 ) ≥ 5 .  Jika  untuk  setiap 𝑣 𝑖 , 𝑣 𝑗 ∈ 𝑈 dengan 𝑑(𝑣 𝑖 , 𝑣 𝑗 ) < 5 ,  maka  terdapat pasangan  titik  bertetangga 𝑣 𝑡 , 𝑣 𝑡+1 ∈ 𝑉(𝑃 𝑛 ) − 𝑈 dengan 𝑑(𝑣 𝑗 , 𝑣 𝑡 ) > 1 atau 𝑑(𝑣 𝑖 , 𝑣 𝑡+1 ) > 1 sehingga |{𝑣 𝑡 , 𝑣 𝑡+1 } ∩ 𝑁(𝑣 𝑗 )| = 0 ≠ 1 .  Berdasarkan  Definisi himpunan pembeda ketetanggaan lokal 𝑈 bukan himpunan pembeda ketetanggaan lokal. Sebaliknya jika terdapat 𝑣 𝑖 , 𝑣 𝑗 ∈ 𝑈 dengan 𝑖 < 𝑗 , 𝑑(𝑣 𝑖 , 𝑣 𝑗 ) ≥ 5 , berdasarkan Lema 2.1 maka 𝑈 bukan himpunan pembeda ketetanggaan lokal.
Oleh  karena  itu 𝑊 merupakan  basis  ketetanggaan  lokal  dari  graf 𝑃 𝑛 dan 𝑑𝑖𝑚 𝐴𝑙 (𝑃 𝑛 ) = ⌈ 𝑛−1 4 ⌉ ∎
Teorema 2.3 [4]. 𝑑𝑖𝑚 𝐴𝑙 (𝐶 𝑛 ) = ⌈ 𝑛 4 ⌉ dengan 𝑛 ≥ 4
Bukti. Misalkan 𝑉(𝐶 𝑛 ) = {𝑣 1 , 𝑣 2 , … , 𝑣 𝑛−1 , 𝑣 𝑛 } , 𝐸(𝐶 𝑛 ) = {(𝑣 𝑖 , 𝑣 𝑛 ) ∪ (𝑣 𝑖 , 𝑣 𝑖+1 ), dengan 𝑖 = 1,2, … , 𝑛 − 1 } , 𝑊 ∈ 𝑉(𝐶 𝑛 ) , dan 𝑊 = {𝑣 1 , 𝑣 5 , … , 𝑣 4(𝑘−1)+1 , … , 𝑣 [4(⌈ 𝑛 4 ⌉−1)+1] } dengan 𝑘 merupakan  urutan  titik  ke- 𝑘 pada 𝑊 dengan 𝑘 ≤ ⌈ 𝑛 4 ⌉ , 𝑘 ∈ ℕ sehingga |𝑊| = ⌈ 𝑛 4 ⌉ . Diambil sebarang 𝑣 𝑖 ∈ 𝑊 pada graf 𝐶 𝑛 maka terdapat 𝑖 = 1,5, … , 4(𝑘 − 1) + 1, … , 4 (⌈ 𝑛 4 ⌉ − 1) + 1 sehingga diperoleh
𝑁(𝑣 𝑖 ) = { {𝑣 2 , 𝑣 𝑛 }, untuk 𝑖 = 1
{𝑣 𝑛−1 , 𝑣 1 }, untuk 𝑖 = 𝑛 {𝑣 4(𝑘−1) , 𝑣 4(𝑘−1)+2 }, untuk 𝑖 = 4(𝑘 − 1) + 1
Terdapat  empat kemungkinan nilai 𝑛 pada graf 𝐶 𝑛 yaitu terdapat 𝑚 ∈ ℕ sehingga 𝑛 = 4𝑚, 𝑛 = 4𝑚 + 1, 𝑛 = 4𝑚 + 2, atau 𝑛 = 4𝑚 + 3 .
i. Untuk 𝑛 = 4𝑚 . Diambil sebarang titik yang bertetangga 𝑥, 𝑦 ∈ 𝑉(𝐶 𝑛 ) − 𝑊 , terdapat tiga kemungkinan yaitu
𝑥 = 𝑣 4(𝑘−1)+2 dan 𝑦 = 𝑣 4(𝑘−1)+3 dengan 𝑘 = 1,2, … , ⌈ 𝑛 4 ⌉ , 𝑥 = 𝑣 4(𝑘−1)−1 dan 𝑦 = 𝑣 4(𝑘−1) dengan 𝑘 = 2,3, … , ⌈ 𝑛 4 ⌉ atau
𝑥 = 𝑣 𝑛 dan 𝑦 = 𝑣 𝑛−1 . Oleh karena itu, diperoleh |{𝑣 4(𝑘−1)+2 , 𝑣 4(𝑘−1)+3 } ∩ 𝑁(𝑣 𝑖 )| = |{𝑣 4(𝑘−1)+2 }| = 1 untuk 𝑘 = 1 , |{𝑣 𝑛 , 𝑣 (𝑛−1) } ∩ 𝑁(𝑣 𝑖 )| = |{𝑣 𝑛 }| = 1 untuk 𝑖 = 1 , |{𝑣 4(𝑘−1)−1 , 𝑣 4(𝑘−1) } ∩ 𝑁(𝑣 𝑖 )| = |{𝑣 4(𝑘−1) }| = 1 untuk 𝑖 = 4(𝑘 − 1) + 1 , atau |{𝑣 4(𝑘−1)+2 , 𝑣 4(𝑘−1)+3 } ∩ 𝑁(𝑣 𝑖 )| = |{𝑣 4(𝑘−1)+2 }| = 1 untuk 𝑖 = 4(𝑘 − 1) + 1 . Berdasarkan uraian diatas 𝑊 merupakan himpunan pembeda ketetanggaan lokal. ii. Untuk 𝑛 = 4𝑚 + 1 dan 𝑛 = 4𝑚 + 2 . Diambil sebarang titik yang bertetangga 𝑥, 𝑦 ∈ 𝑉(𝐶 𝑛 ) − 𝑊 , terdapat dua kemungkinan yaitu 𝑥 = 𝑣 4(𝑘−1)+2 dan 𝑦 = 𝑣 4(𝑘−1)+3 dengan 𝑘 = 1,2, … , ⌈ 𝑛 4 ⌉ − 1 , atau 𝑥 = 𝑣 4(𝑗−1)−1 dan 𝑦 = 𝑣 4(𝑗−1) dengan 𝑗 = 2,3, … , ⌈ 𝑛 4 ⌉ .
Oleh karena itu: |{𝑣 4(𝑘−1)+2 , 𝑣 4(𝑘−1)+3 } ∩ 𝑁(𝑣 𝑖 )| = |{𝑣 4(𝑘−1)+2 }| = 1 untuk 𝑘 = 1 , |{𝑣 4(𝑘−1)−1 , 𝑣 4(𝑘−1) } ∩ 𝑁(𝑣 𝑖 )| = |{𝑣 4(𝑘−1) }| = 1 untuk 𝑖 = 4𝑚 + 1 dan 𝑘 = 𝑚 + 1 , |{𝑣 4(𝑘−1)−1 , 𝑣 4(𝑘−1) } ∩ 𝑁(𝑣 𝑖 )| = |{𝑣 4(𝑘−1) }| = 1 untuk 𝑖 = 4(𝑘 − 1) + 1 , atau |{𝑣 4(𝑘−1)+2 , 𝑣 4(𝑘−1)+3 } ∩ 𝑁(𝑣 𝑖 )| = |{𝑣 4(𝑘−1)+2 }| = 1 untuk 𝑖 = 4(𝑘 − 1) + 1 . Berdasarkan  uraian  di  atas 𝑊 merupakan  himpunan  pembeda  ketetanggaan  lokal dengan |𝑊| = ⌈ 𝑛 4 ⌉ iii. Sedangkan  untuk 𝑛 = 4𝑚 + 3 .  Diambil  sebarang  titik  yang  bertetangga 𝑥, 𝑦 ∈ 𝑉(𝐶 𝑛 ) − 𝑊 , terdapat dua kemungkinan yaitu 𝑥 = 𝑣 4(𝑘−1)+2 dan 𝑦 = 𝑣 4(𝑘−1)+3 dengan 𝑘 = 1,2, … , ⌈ 𝑛 4 ⌉ atau 𝑥 = 𝑣 4(𝑘−1)−1 dan 𝑦 = 𝑣 4(𝑘−1) dengan 𝑘 = 2,3, … , ⌈ 𝑛 4 ⌉ .
Oleh karena itu: |{𝑣 4(𝑘−1)+2 , 𝑣 4(𝑘−1)+3 } ∩ 𝑁(𝑣 𝑖 )| = |{𝑣 4(𝑘−1)+2 }| = 1 untuk 𝑘 = 1 , atau
|{𝑣 4(𝑘−1)−1 , 𝑣 4(𝑘−1) } ∩ 𝑁(𝑣 𝑖 )| = |{𝑣 4(𝑘−1) }| = 1 untuk 𝑖 = 4(𝑘 − 1) + 1 . Berdasarkan  uraian  di  atas 𝑊 merupakan  himpunan  pembeda  ketetanggaan  lokal dengan |𝑊| = ⌈ 𝑛 4 ⌉
Selanjutnya  ditunjukkan  bahwa 𝑊 merupakan  himpunan  pembeda  ketetanggaan  lokal minimal.  Diambil  sebarang 𝑈 ⊆  𝑉(𝐶 𝑛 ) dengan |𝑈| < |𝑊| .  Terdapat  tiga  kasus  yaitu 𝑛 = 4 , 4 < 𝑛 ≤ 8 , atau 𝑛 > 8
(i) Untuk 𝑛 = 4 , |𝑈| < |𝑊| = ⌈ 𝑛 4 ⌉ = 1 akibatnya 𝑈 = ∅ .  Berdasarkan  Definisi himpunan  pembeda  ketetanggaan  lokal  maka 𝑈 bukan  merupakan  himpunan pembeda ketetanggaan lokal.
(ii) Untuk 4 < 𝑛 ≤ 8 , |𝑈| < |𝑊| = ⌈ 𝑛 4 ⌉ = 2 akibatnya |𝑈| = 1 .  Misalkan 𝑈 = {𝑣 𝑖 } . Karena |𝑉(𝐶 𝑛 ) − 𝑈| ≥ 4 maka  terdapat  pasangan  titik  bertetanga 𝑣 𝑗 , 𝑣 𝑗+1 ∈
𝑉(𝑃 𝑛 ) − 𝑈 dengan 𝑑(𝑣 𝑖 , 𝑣 𝑗 ) > 1 atau 𝑑(𝑣 𝑖 , 𝑣 𝑗+1 ) > 1 sehingga |{𝑣 𝑗 , 𝑣 𝑗+1 } ∩ 𝑁(𝑣 𝑖 )| = 0 ≠ 1 .  Berdasarkan  Definisi  himpunan  pembeda  ketetanggaan  lokal maka 𝑈 bukan merupakan himpunan pembeda ketetanggaan lokal.
(iii) Untuk 𝑛 > 8 . Terdapat 𝑣 𝑖 , 𝑣 𝑗 ∈ 𝑈 dengan 𝑖 < 𝑗, 𝑙(𝑣 𝑖 − 𝑣 𝑗 ) > 5 . Berdasarkan Lema 2.1 𝑈 bukan himpunan pembeda ketetanggaan lokal.
Oleh karena itu 𝑊 merupakan basis ketetanggaan lokal dan 𝑑𝑖𝑚 𝐴𝑙 (𝐶 𝑛 ) = ⌈ 𝑛 4 ⌉ ∎
Teorema 2.4 [4] . 𝑑𝑖𝑚 𝐴𝑙 (𝑆 𝑛 ) = 1 dengan 𝑛 ≥ 2
Bukti. Misalkan 𝑉(𝐶 𝑛 ) = {𝑣 1 , 𝑣 2 , … , 𝑣 𝑛−1 , 𝑣 𝑛 } , 𝐸(𝐶 𝑛 ) = {(𝑣 𝑖 , 𝑣 𝑛 ) ∪ (𝑣 𝑖 , 𝑣 𝑖+1 )|𝑖 = 1,2, … , 𝑛 − 1 } , dan 𝑊 = {𝑣 1 } . Diambil sebarang titik yang bertetangga 𝑥, 𝑦 ∈ 𝑉(𝑆 𝑛 ) − 𝑊 , yaitu 𝑥 = 𝑣 0 dan 𝑦 = 𝑣 𝑟 dengan 𝑟 = 2,3, … , 𝑛 . Karena |{𝑣 0 , 𝑣 𝑟 } ∩ 𝑁(𝑣 𝑖 )| = |{𝑣 0 }| = 1 , maka 𝑊 merupakan himpunan pembeda ketetanggaan lokal. Karena |𝑊| = 1 maka 𝑑𝑖𝑚 𝐴𝑙 (𝑆 𝑛 ) = 1 ∎
Teorema 2.5 [4] . 𝑑𝑖𝑚 𝐴𝑙 (𝐺) = 𝑛 − 1 jika dan hanya jika 𝐺 ≅ 𝐾 𝑛 dengan 𝑛 ≥ 2 .
Bukti. (⇐) Misalkan 𝑉(𝐾 𝑛 ) = {𝑣 1 , 𝑣 2 , … , 𝑣 𝑛 } , 𝐸(𝐾 𝑛 ) = {(𝑣 𝑖 , 𝑣 𝑗 ) dengan 𝑖, 𝑗 = 1,2, … , 𝑛 𝑑𝑎𝑛 𝑖 ≠ 𝑗} dengan 𝑛 ≥ 2 ,  dan 𝑊 = {𝑣 1 , 𝑣 2 , … , 𝑣 𝑛−1 } sehingga |𝑊| = 𝑛 − 1 . Karena tidak terdapat pasangan titik yang bertetangga 𝑥, 𝑦 ∈ 𝑉(𝐾 𝑛 ) − 𝑊 , maka 𝑊 adalah himpunan pembeda ketetanggaan lokal. Selanjutnya ditunjukkan bahwa |𝑊| merupakan basis  ketetanggaan  lokal.  Dipilih 𝑈 ⊆  𝑉(𝐾 𝑛 ) dengan |𝑈| < |𝑊| .  Terdapat  dua  kasus yaitu 𝑛 = 2 atau 𝑛 > 2 .
(i) Untuk 𝑛 = 2 , |𝑈| < |𝑊| = 𝑛 − 1 = 1 akibatnya 𝑈 = ∅ .  Berdasarkan  Definisi himpunan  pembeda  ketetanggaan  lokal  maka 𝑈 bukan  merupakan  himpunan pembeda ketetanggaan lokal.
(ii) Untuk 𝑛 = 3 , |𝑈| < |𝑊| = 𝑛 − 1 = 2 akibatnya |𝑈| = 1 .  Tanpa  mengurangi keumuman  bukti  misalkan 𝑈 = {𝑣 1 } .  Karena  pasangan  titik  bertetangga 𝑣 2 , 𝑣 3 ∈ 𝑉(𝐾 𝑛 ) − 𝑈 dan |{𝑣 2 , 𝑣 3 } ∩ 𝑁(𝑣 1 )| = 2 ≠ 1 ,  maka 𝑈 bukan  merupakan  himpunan pembeda ketetanggaan lokal.
(iii) Untuk 𝑛 > 3 ,  untuk  setiap 𝑣 𝑖 ∈ 𝑈 maka  untuk  setiap  pasangan  titik  bertetangga 𝑣 𝑘 , 𝑣 𝑡 ∈ 𝑉(𝐾 𝑛 ) − 𝑈 , 𝑣 𝑘 , 𝑣 𝑡 ∈ 𝑁(𝑣 𝑖 ) sehingga |{𝑣 𝑘 , 𝑣 𝑡 } ∩ 𝑁(𝑣 𝑖 )| = 2 ≠ 1 . Berdasarkan  Definisi  himpunan  pembeda  ketetanggaan  lokal  maka 𝑈 bukan merupakan himpunan pembeda ketetanggaan lokal.
Oleh karena itu 𝑊 merupakan basis ketetanggaan lokal. Terbukti bahwa 𝑑𝑖𝑚 𝐴𝑙 (𝐾 𝑛 ) = 𝑛 − 1 . Dengan demikian jika 𝐺 ≅ 𝐾 𝑛 maka 𝑑𝑖𝑚 𝐴𝑙 (𝐺) = 𝑛 − 1 .
(⇒) Misalkan 𝑑𝑖𝑚 𝐴𝑙 (𝐺) = 𝑛 − 1 dan andaikan 𝐺 ≇ 𝐾 𝑛 , sehingga terdapat 𝑣 𝑖 , 𝑣 𝑘 ∈ 𝑉(𝐺) dengan (𝑣 𝑖 , 𝑣 𝑘 ) ∉ 𝐸(𝐺) . Dipilih 𝑊′ = 𝑉(𝐺) − {𝑣 𝑖 , 𝑣 𝑘 } sehingga 𝑉(𝐺) − 𝑊 ′ = {𝑣 𝑖 , 𝑣 𝑘 } . Karena  tidak  terdapat  pasangan  titik  bertetangga 𝑥, 𝑦 ∈ 𝑉(𝐺) − 𝑊′ ,  maka 𝑊′ adalah himpunan  pembeda  ketetanggaan  lokal  dengan |𝑊′| = 𝑛 − 2 ,  kontradiksi  dengan 𝑑𝑖𝑚 𝐴𝑙 (𝐺) = 𝑛 − 1 .
Berdasarkan uraian diatas, terbukti bahwa 𝑑𝑖𝑚 𝐴𝑙 (𝐺) = 𝑛 − 1 jika dan hanya jika 𝐺 ≅ 𝐾 𝑛 dengan 𝑛 ≥ 2 ∎
Saputro dkk [7] menyajikan definisi operasi comb pada graf. Graf 𝐺𝐨𝐻 merupakan graf hasil kali comb dari graf terhubung 𝐺 dan 𝐻 . Misalkan 𝑉(𝐺) = {𝑣 1 , 𝑣 2 , … , 𝑣 𝑛 } dan 𝑉(𝐻) = {𝑢 1 , 𝑢 2 , … , 𝑢 𝑚 } dengan 𝑛, 𝑚 ≥ 2 . Titik cangkok pada 𝐻 diasumsikan sebagai 𝑢 1 . Titik 𝑣 𝑖 ∈ 𝑉(𝐺) di graf 𝐺𝐨𝐻 dinotasikan sebagai 𝑣 𝑖1 , sedangkan titik 𝑢 𝑗 ∈ 𝑉(𝐻), 𝑗 ≠ 1 di  graf 𝐺𝐨𝐻 dinotasikan  sebagai 𝑣 𝑖𝑗 .  Himpunan 𝐼 = {𝑣 𝑖1 |𝑖 = 1,2, … , 𝑛} disebut  induk, sedangkan himpunan daun ke 𝑖 disebut 𝐻 𝑖 = {𝑣 𝑖2 , 𝑣 𝑖3 , … , 𝑣 𝑖𝑚 |𝑖 = 1,2, … , 𝑛} .
Misalkan G dan H adalah graf terhubung, 𝑉(𝐺) = {𝑣 1 , 𝑣 2 , 𝑣 3 , … , 𝑣 𝑛 } , dan o adalah titik  cangkok  di H .  Graf G  k-comb H dinotasikan  dengan 𝐺𝛐 𝒌 𝐻 adalah  graf  yang diperoleh dengan mengambil  satu salinan G dan nk salinan dari H , yaitu H 11 , H 12 , H 13 ,..., H 1 k , H 21 , H 22 , H 23 , ..., H 2 k , ...., H n 1 , H n 2 , H n 3 , ..., H nk dan merekatkan setiap salinan ke- ij , 𝑖 = 1,2,3, … , 𝑛 ; j = 1, 2, 3, ... k dari graf H di titik cangkok 𝑜 𝑖𝑗 pada titik 𝑣 𝑖 dari graf G , dengan 𝑜 𝑖𝑗 merupakan salinan titik o di 𝐻 𝑖𝑗 [8]. Apabila k = 1 maka berlaku 𝐺𝛐 𝒌 𝐻 = 𝐺𝛐𝐻 . Sedangkan graf 𝐺𝐨 𝒌 𝐻 merupakan graf hasil kali k -comb dari graf terhubung 𝐺 dan 𝐻 . Untuk 𝑘 = 1 , penamaan titik mengikuti  graf 𝐺𝒐𝐻 . Untuk 𝑘 ≥ 2 , misalkan 𝑉(𝐺) = {𝑣 1 , 𝑣 2 , … , 𝑣 𝑛 } dan 𝑉(𝐻) = {𝑢 1 , 𝑢 2 , … , 𝑢 𝑚 } dengan 𝑛, 𝑚 ≥ 2 .  Titik  cangkok  pada 𝐻 diasumsikan  sebagai 𝑢 1 .  Titik 𝑣 𝑖 ∈ 𝑉(𝐺) di  graf 𝐺𝐨 𝒌 𝐻 dinotasikan  sebagai 𝑣 𝑖101 , sedangkan titik 𝑢 𝑗 ∈ 𝑉(𝐻), 𝑗 ≠ 1 di graf 𝐺𝐨 𝒌 𝐻 dinotasikan sebagai 𝑣 𝑖𝑡𝑗 . Himpunan 𝐼 = {𝑣 𝑖01 |𝑖 = 1,2, … , 𝑛} disebut  induk,  sedangkan 𝑘 salinan  daun  ke 𝑖 disebut 𝐻 𝑖𝑡 = {𝑣 𝑖𝑡2 , 𝑣 𝑖𝑡3 , … , 𝑣 𝑖𝑡𝑚 } dengan 𝑖 = 1,2, … , 𝑛 dan 𝑡 = 1,2, … , 𝑘 .
Teorema 2.6 Misalkan 𝐺 graf terhubung berordo 𝑛 ≥ 2 dan graf 𝐾 𝑚 berordo 𝑚 ≥ 3 . Jika 𝛾(𝐺) merupakan bilangan dominasi pada graf 𝐺, maka
𝑑𝑖𝑚 𝐴𝐿 (𝐺𝐨𝐾 𝑚 ) = |𝑉(𝐺)|(𝑑𝑖𝑚 𝐴𝑙 (𝐾 𝑚 ) − 1) + 𝛾(𝐺)
Bukti. Misalkan 𝑆 = {𝑣 𝑛1 , 𝑣 𝑛2 , … , 𝑣 𝑛𝛾(𝐺) } ⊆ 𝑉(𝐺) merupakan  sebarang  himpunan dominasi dari graf 𝐺 , selanjutnya berdasarkan penamaan titik pada graf hasil operasi kali comb  himpunan 𝑆 dapat  ditulis  sebagai 𝑆 ∗ = {𝑣 𝑛 1 1 , 𝑣 𝑛 2 1 , … , 𝑣 𝑛 𝛾(𝐺) 1 } .  Berdasarkan Teorema  2.5,  himpunan 𝐵 𝑖 = {𝑣 𝑖1 , 𝑣 𝑖2 , … , 𝑣 𝑖(𝑚−1) } dengan 𝑖 = 1,2, … , 𝑛 merupakan basis ketetanggaan lokal graf 𝐾 𝑚 𝑖 . Dipilih 𝑊 = 𝑆 ∗ ⋃ (𝐵 𝑖 𝑛 𝑖=1 − {𝑣 𝑖1 }) . Diambil sebarang
titik yang bertetangga 𝑥, 𝑦 ∈ 𝑉(𝐺𝐨𝐾 𝑚 ) − 𝑊 , terdapat dua kasus yaitu 𝑥, 𝑦 ∈ 𝐼 − 𝑆 ∗ atau 𝑥 ∈ 𝐼 − 𝑆 ∗ dan 𝑦 ∈ (𝐵 𝑖 − {𝑣 𝑖1 }) .
(i) Jika 𝑥, 𝑦 ∈ 𝐼 − 𝑆 ∗ , 𝑥 = 𝑣 𝑟1 dan 𝑦 = 𝑣 𝑘1 dengan 𝑟, 𝑘 ≠ 𝑛 𝑖 , 𝑖 = 1,2, … , 𝛾(𝐺) . Dipilih 𝑣 𝑟2 ∈ 𝑊 .  Karena 𝑑(𝑣 𝑟1 , 𝑣 𝑟2 ) = 1 atau 𝑑(𝑣 𝑘1 , 𝑣 𝑟2 ) > 1 maka |𝑁(𝑣 𝑟2 ) ∩ {𝑣 𝑟1 , 𝑣 𝑘1 }| = |{𝑣 𝑟1 }| = 1 .
(ii) Jika 𝑥 ∈ 𝐼 − 𝑆 ∗ dan 𝑦 ∈ (𝐵 𝑖 − {𝑣 𝑖1 }) ,  sehingga 𝑥 = 𝑣 𝑟1 dan 𝑦 = 𝑣 𝑟𝑚 dengan 𝑟 ≠ 𝑛 𝑖 , 𝑖 = 1,2, … , 𝛾(𝐺) .  Karena 𝑆 ∗ merupakan  himpunan  dominasi  dari  induk,  maka terdapat 𝑣 𝑛 𝑘 1 ∈ 𝑆 ∗ .  Karena 𝑑(𝑣 𝑟1 , 𝑣 𝑛 𝑘 1 ) = 1 dan 𝑑(𝑣 𝑟𝑚 , 𝑣 𝑛 𝑘 1 ) > 1 maka |𝑁(𝑣 𝑛 𝑘 1 ) ∩ {𝑣 𝑟1 , 𝑣 𝑟𝑚 }| = |{𝑣 𝑟1 }| = 1 .
Oleh  karena  itu 𝑊 merupakan  himpunan  pembeda  ketetanggaan  lokal.  Selanjutnya ditunjukkan  bahwa 𝑊 merupakan  basis  ketetanggaan  lokal.  Diambil  sebarang 𝑊 ′ ⊆ 𝑉(𝐺𝐨𝐾 𝑚 ) , |𝑊 ′ | < |𝑊| . Terdapat dua kemungkinan yaitu 𝑊 ′ = 𝐼′ ⋃ 𝐻′ 𝑛 𝑖=1 dengan 𝐼 ′ ⊆ 𝐼 , |𝐼′| < 𝛾(𝐺) ,  dan |𝐻′| = |𝐵 𝑖 − {𝑣 𝑖1 }| atau 𝑊 ′ = 𝐼′ ⋃ 𝐻′ 𝑛 𝑖=1 dengan |𝐼′| = 𝛾(𝐺), 𝐻′ ⊆ ⋃ 𝐾 𝑚 𝑖 𝑛 𝑖=1 , dan |𝐻′| < |𝐵 𝑖 − {𝑣 𝑖1 }| .
a. Untuk 𝑊 ′ = 𝐼′ ⋃ 𝐻′ 𝑛 𝑖=1 , dengan 𝐼 ′ ⊆ 𝐼 , |𝐼′| < 𝛾(𝐺) , dan |𝐻′| = |𝐵 𝑖 − {𝑣 𝑖1 }| . Karena 𝐼 ′ bukan merupakan himpunan dominasi minimal, maka terdapat titik 𝑣 𝑟1 ∈ 𝐼 − 𝐼 ′ sehingga 𝑑(𝑣 𝑟1 , 𝑣 𝑛 𝑘 1 ) > 1, 𝑣 𝑛 𝑘 1 ∈ 𝐼 ′ . Terdapat pasangan titik bertetangga 𝑣 𝑟1 , 𝑣 𝑟ℎ ∈ 𝑉(𝐺𝐨𝐾 𝑚 ) − 𝑊′ dengan ℎ ≠ 1 .  Diambil  sebarang 𝑥 ∈ 𝑊 ′ ,  maka  terdapat  dua kemungkinan yaitu 𝑥 = 𝑣 𝑛 𝑘 1 , 𝑣 𝑛 𝑘 1 ∈ 𝐼 ′ atau = 𝑣 𝑖ℎ , ℎ ≠ 1, 𝑣 𝑖ℎ ∈ 𝐻 ′ .
i. Jika 𝑥 = 𝑣 𝑛 𝑘 1 maka 𝑣 𝑟1 , 𝑣 𝑟ℎ ∉ 𝑁(𝑥) . Oleh karena itu |{𝑣 𝑟1 , 𝑣 𝑟ℎ } ∩ 𝑁(𝑥)| ≠ 1 . ii. Jika 𝑥 = 𝑣 𝑖ℎ , ℎ ≠ 1 maka  terdapat  dua  kemungkinan  yaitu 𝑣 𝑟1 , 𝑣 𝑟ℎ ∉ 𝑁(𝑥) untuk 𝑖 ≠ 𝑟 atau 𝑣 𝑟1 , 𝑣 𝑟ℎ ∈ 𝑁(𝑥) untuk 𝑖 = 𝑟 . Akibatnya |{𝑣 𝑟1 , 𝑣 𝑟ℎ } ∩ 𝑁(𝑥)| ≠ 1 . Oleh karena itu 𝑊′ bukan himpunan pembeda ketetanggaan lokal.
b. Selanjutnya untuk 𝑊 ′ = 𝐼′ ⋃ 𝐻′ 𝑛 𝑖=1 , dengan 𝐼 ′ ⊆ 𝐼 , |𝐼′| = 𝛾(𝐺) , |𝐻′| < |𝐵 𝑖 − {𝑣 𝑖1 }| , dan 𝐻′ ⊆ ⋃ 𝐾 𝑚 𝑖 𝑛 𝑖=1 . Terdapat 𝐾 𝑚 𝑖 sehingga maksimal terdapat (|𝐵 𝑖 − {𝑣 𝑖1 }| − 1) titik yang  menjadi  anggota 𝑊 ′ .  Tanpa  mengurangi  keumuman  bukti,  misalkan 𝑖 = 1 sehingga  maksimal  terdapat (|𝐵 1 − {𝑣 11 }| − 1) titik  yang  menjadi  anggota 𝑊 ′ . Akibatnya terdapat  pasangan titik bertetangga 𝑣 12 , 𝑣 13 ∈ 𝑉(𝐺𝐨𝐾 𝑚 ) − 𝑊′ . Diambil sebarang 𝑥 ∈ 𝑊 ′ ,  maka  terdapat  dua  kemungkinan  yaitu 𝑥 = 𝑣 𝑛 𝑘 1 , 𝑣 𝑛 𝑘 1 ∈ 𝐼 ′ atau 𝑥 = 𝑣 𝑖𝑡 , 𝑡 = (4,5, … , 𝑚), 𝑣 𝑖𝑡 ∈ 𝐻 ′ . i. Jika 𝑥 = 𝑣 𝑛 𝑘 1 maka 𝑣 12 , 𝑣 13 ∉ 𝑁(𝑥) . Akibatnya |{𝑣 12 , 𝑣 13 } ∩ 𝑁(𝑥)| ≠ 1 . ii. Sedangkan  jika 𝑥 = 𝑣 𝑖𝑡 maka 𝑣 12 , 𝑣 13 ∈ 𝑁(𝑥) .  Akibatnya |{𝑣 12 , 𝑣 13 } ∩ 𝑁(𝑥)| ≠ 1 . Oleh karena itu 𝑊′ bukan himpunan pembeda ketetanggaan lokal.
Berdasarkan uraian di atas 𝑊′ bukan himpunan pembeda ketetanggaan lokal. Oleh karena itu 𝑊 merupakan basis ketetanggaan lokal dari graf 𝐺𝐨𝐾 𝑚 . Jadi 𝑑𝑖𝑚 𝐴𝑙 (𝐺𝐨𝐾 𝑚 ) = |𝑊| = |𝑉(𝐺)|(𝑑𝑖𝑚 𝐴𝑙 (𝐾 𝑚 ) − 1) + 𝛾(𝐺) . ∎
Munawaroh [9] menyajikan definisi operasi kali comb tingkat 𝑘 dari graf 𝐺 dan graf 𝐻 yang dinotasikan dengan 𝐺𝐨 𝑘 𝐻 .
Akibat 2.7. Misalkan 𝐺 graf terhubung berordo 𝑛 ≥ 2 dan graf 𝐾 𝑚 berordo 𝑚 ≥ 3 . Jika 𝑘 ≥ 1 maka
𝑑𝑖𝑚 𝐴𝐿 (𝐺𝐨 𝑘 𝐾 𝑚 ) = |𝑉(𝐺𝐨 𝑘−1 𝐾 𝑚 )|(𝑑𝑖𝑚 𝐴𝑙 (𝐾 𝑚 ) − 1) + 𝛾(𝐺𝐨 𝑘−1 𝐾 𝑚 )
Bukti. Misalkan 𝐺 ′ = 𝐺𝐨 𝑘−1 𝐾 𝑚 ,  akibatnya 𝐺𝐨 𝑘 𝐾 𝑚 =  𝐺′𝐨𝐾 𝑚 .  Bedasarkan  Teorema 2.1, diperoleh 𝑑𝑖𝑚 𝐴𝑙 (𝐺𝐨 𝑘 𝐾 𝑚 ) = |𝑉(𝐺𝐨 𝑘−1 𝐾 𝑚 )|(𝑑𝑖𝑚 𝐴𝑙 (𝐾 𝑚 ) − 1) + 𝛾(𝐺𝐨 𝑘−1 𝐾 𝑚 ) . ∎
Teorema 2.8. Misalkan 𝐺 adalah graf terhubung berorodo 𝑛 ≥ 2 dan 𝐻 adalah graf 𝐾 𝑚 berordo 𝑚 ≥ 3 .  Jika 𝛾(𝐺) merupakan  bilangan  dominasi  dari  graf 𝐺 dan 𝑘 > 1 maka
𝑑𝑖𝑚 𝐴𝐿 (𝐺𝐨 𝒌 𝐾 𝑚 ) = 𝑘|𝑉(𝐺)|(𝑑𝑖𝑚 𝐴𝐿 (𝐾 𝑚 ) − 1) + 𝛾(𝐺)
Bukti. Misalkan 𝑆 = {𝑣 𝑛1 , 𝑣 𝑛2 , … , 𝑣 𝑛𝛾(𝐺) } ⊆ 𝑉(𝐺) merupakan  himpunan  dominasi minimal dari graf 𝐺 , selanjutnya berdasarkan penamaan titik pada graf hasil operasi kali 𝑘 -comb himpunan 𝑆 dapat ditulis sebagai 𝑆 ∗ = {𝑣 𝑛 1 01 , 𝑣 𝑛 2 01 , … , 𝑣 𝑛 𝛾(𝐺) 01 } . Berdasarkan Teorema  2.5,  himpunan 𝐵 𝑖𝑡 = {𝑣 𝑖01 , 𝑣 𝑖𝑡2 , … , 𝑣 𝑖𝑡(𝑚−1) } dengan 𝑖 = 1,2, … , 𝑛 dan 𝑡 = 1,2, … , 𝑘 merupakan  basis  ketetanggaan  lokal  graf 𝐾 𝑚 𝑖𝑡 .  Dipilih 𝑊 = 𝑆 ∗ ⋃ (𝐵 𝑖𝑡 𝑛𝑘 𝑖=1 − {𝑣 𝑖01 }) .  Diambil  sebarang  titik  yang  bertetangga 𝑥, 𝑦 ∈ 𝑉(𝐺𝐨 𝒌 𝐾 𝑚 ) − 𝑊 ,  terdapat  dua kasus yaitu 𝑥, 𝑦 ∈ 𝐼 − 𝑆 ∗ atau 𝑥 ∈ 𝐼 − 𝑆 ∗ dan 𝑦 ∈ (𝐵 𝑖𝑡 − {𝑣 𝑖01 }) .
i. Jika 𝑥, 𝑦 ∈ 𝐼 − 𝑆 ∗ , 𝑥 = 𝑣 𝑟01 dan 𝑦 = 𝑣 𝑘01 dengan 𝑟, 𝑘 ≠ 𝑛 𝑖 , 𝑖 = 1,2, … , 𝛾(𝐺) . Dipilih 𝑣 𝑟𝑡2 ∈ 𝑊 dengan 𝑡 = 1,2, … , 𝑘 .  Karena 𝑑(𝑣 𝑟01 , 𝑣 𝑟𝑡2 ) = 1 atau 𝑑(𝑣 𝑘01 , 𝑣 𝑟𝑡2 ) > 1 maka |𝑁(𝑣 𝑟𝑡2 ) ∩ {𝑣 𝑟01 , 𝑣 𝑘01 }| = |{𝑣 𝑟01 }| = 1 . ii. Jika 𝑥 ∈ 𝐼 − 𝑆 ∗ dan 𝑦 ∈ (𝐵 𝑖𝑡 − {𝑣 𝑖01 }) , sehingga 𝑥 = 𝑣 𝑟01 dan 𝑦 = 𝑣 𝑟𝑡𝑚 dengan 𝑟 ≠ 𝑛 𝑖 , 𝑖 = 1,2, … , 𝛾(𝐺) dan 𝑡 = 1,2, … , 𝑘 .  Karena 𝑆 ∗ merupakan  himpunan  dominasi minimal  dari  induk,  maka  terdapat 𝑣 𝑛 𝑘 01 ∈ 𝑆 ∗ .  Karena 𝑑(𝑣 𝑟01 , 𝑣 𝑛 𝑘 01 ) = 1 dan 𝑑(𝑣 𝑟𝑡𝑚 , 𝑣 𝑛 𝑘 01 ) > 1 maka |𝑁(𝑣 𝑛 𝑘 01 ) ∩ {𝑣 𝑟01 , 𝑣 𝑟𝑡𝑚 }| = |{𝑣 𝑟01 }| = 1 .
Berdasarkan uraian diatas 𝑊 merupakan himpunan pembeda ketetanggaan lokal.
Selanjutnya ditunjukkan bahwa 𝑊 merupakan basis ketetanggaan lokal minimal. Diambil sebarang 𝑊 ′ ⊆ 𝑉(𝐺𝐨 𝒌 𝐾 𝑚 ) , |𝑊 ′ | < |𝑊| .  Terdapat  dua  kemungkinan  yaitu 𝑊 ′ = 𝐼′ ⋃ 𝐻′ 𝑛 𝑖=1 dengan 𝐼 ′ ⊆ 𝐼 , |𝐼′| < 𝛾(𝐺) ,  dan |𝐻′| = |𝐵 𝑖𝑡 − {𝑣 𝑖01 }| atau 𝑊 ′ = 𝐼′ ⋃ 𝐻′ 𝑛𝑘 𝑖=1
dengan |𝐼′| = 𝛾(𝐺), 𝐻′ ⊆ ⋃ 𝐾 𝑚 𝑖𝑡 𝑛𝑘 𝑖=1 , dan |𝐻′| < |𝐵 𝑖𝑡 − {𝑣 𝑖01 }| .
a. Untuk 𝑊 ′ = 𝐼′ ⋃ 𝐻′ 𝑛𝑘 𝑖=1 dengan 𝐼 ′ ⊆ 𝐼 , |𝐼′| < 𝛾(𝐺) ,  dan |𝐻′| = |𝐵 𝑖𝑡 − {𝑣 𝑖01 }| . Karena 𝐼 ′ bukan merupakan himpunan dominasi minimal, maka terdapat titik 𝑣 𝑟01 ∈ 𝐼 − 𝐼′ sehingga 𝑑(𝑣 𝑟01 , 𝑣 𝑛 𝑘 01 ) > 1, 𝑣 𝑛 𝑘 01 ∈ 𝐼′ . Terdapat pasangan titik bertetangga 𝑣 𝑟01 , 𝑣 𝑟𝑡ℎ ∈ 𝑉(𝐺𝐨 𝒌 𝐾 𝑚 ) − 𝑊′ dengan ℎ ≠ 1 .  Diambil  sebarang 𝑥 ∈ 𝑊 ′ ,  maka terdapat dua kemungkinan yaitu 𝑥 = 𝑣 𝑛 𝑘 01 , 𝑣 𝑛 𝑘 01 ∈ 𝐼 ′ atau 𝑥 = 𝑣 𝑖𝑡ℎ , ℎ = 2,3 … , 𝑚 . Jika 𝑥 = 𝑣 𝑛 𝑘 01 maka 𝑣 𝑟01 , 𝑣 𝑟𝑡ℎ ∉ 𝑁(𝑥) .  Sedangkan  jika 𝑥 = 𝑣 𝑖𝑡ℎ , ℎ ≠ 1 maka terdapat  dua  kemungkinan  yaitu 𝑣 𝑟01 , 𝑣 𝑟𝑡ℎ ∉ 𝑁(𝑥) untuk 𝑖 ≠ 𝑟 atau 𝑣 𝑟01 , 𝑣 𝑟𝑡ℎ ∈ 𝑁(𝑥) untuk 𝑖 = 𝑟 . Akibatnya |{𝑣 𝑟01 , 𝑣 𝑟𝑡ℎ } ∩ 𝑁(𝑥)| ≠ 1 . Oleh karena itu 𝑊′ bukan himpunan pembeda ketetanggaan lokal.
b. Selanjutnya  untuk 𝑊 ′ = 𝐼′ ⋃ 𝐻′ 𝑛 𝑖=1 , 𝑊 ′ = 𝐼′ ⋃ 𝐻′ 𝑛𝑘 𝑖=1 dengan |𝐼′| = 𝛾(𝐺), 𝐻′ ⊆
⋃ 𝐾 𝑚 𝑖𝑡 𝑛𝑘 𝑖=1 ,  dan |𝐻′| < |𝐵 𝑖𝑡 − {𝑣 𝑖01 }| .  Terdapat 𝐾 𝑚 𝑖𝑡 sehingga  maksimal  terdapat |𝐵 𝑖𝑡 − {𝑣 𝑖01 }| − 1 titik  yang  menjadi  anggota 𝑊 ′ .  Tanpa  mengurangi  keumuman bukti, misalkan 𝑖 = 1 dan 𝑡 = 1 sehingga maksimal  terdapat (|𝐵 11 − {𝑣 101 }| − 1) titik  yang  menjadi  anggota 𝑊 ′ .  Akibatnya  terdapat  pasangan  titik  bertetangga 𝑣 11ℎ , 𝑣 11𝑞 ∈ 𝑉(𝐺𝐨 𝒌 𝐾 𝑚 ) − 𝑊′ dengan ℎ, 𝑞 ≠ 1, ℎ ≠ 𝑞 .  Diambil  sebarang 𝑥 ∈ 𝑊 ′ , maka  terdapat  dua  kemungkinan  yaitu 𝑥 = 𝑣 𝑛 𝑘 01 , 𝑣 𝑛 𝑘 01 ∈ 𝐼 ′ atau 𝑥 = 𝑣 𝑖𝑡𝑝 , 𝑝 ≠ 1, 𝑝 ≠ ℎ, 𝑝 ≠ 𝑞 , dan 𝑣 𝑖𝑡𝑝 ∈ 𝐻 ′ . i. Jika 𝑥 = 𝑣 𝑛 𝑘 01 maka 𝑣 𝑖𝑡ℎ , 𝑣 𝑖𝑡𝑞 ∉ 𝑁(𝑥) . Akibatnya |{𝑣 11ℎ , 𝑣 11𝑞 } ∩ 𝑁(𝑥)| ≠ 1 . ii. Sedangkan  jika 𝑥 = 𝑣 𝑖𝑡𝑝 maka 𝑣 11ℎ , 𝑣 11𝑞 ∈ 𝑁(𝑥) .  Akibatnya |{𝑣 11ℎ , 𝑣 11𝑞 } ∩ 𝑁(𝑥)| ≠ 1 .
Oleh karena itu 𝑊′ bukan himpunan pembeda ketetanggaan lokal.
Berdasarkan uraian di atas 𝑊′ bukan himpunan pembeda ketetanggaan lokal. Oleh karena itu 𝑊 merupakan  basis  ketetanggaan  lokal  dari  graf 𝐺𝐨 𝒌 𝐾 𝑚 .  Jadi 𝑑𝑖𝑚 𝐴𝑙 (𝐺𝐨 𝒌 𝐾 𝑚 ) = |𝑊| = 𝑘|𝑉(𝐺)|(𝑑𝑖𝑚 𝐴𝑙 (𝐾 𝑚 ) − 1) + 𝛾(𝐺) ∎
Teorema 2.9. Misalkan 𝐺 graf terhubung berordo 𝑛 ≥ 2 , graf 𝑆 𝑚 berordo 𝑚 ≥ 2 . Jika titik cangkok 𝑜 bukan merupakan titik dominasi pada graf 𝑆 𝑚 maka
𝑑𝑖𝑚 𝐴𝐿 (𝐺𝐨𝑆 𝑚 ) = |𝑉(𝐺)|
Bukti. Misalkan 𝑊 = 𝐼 = {𝑣 𝑖1 |𝑖 = 1,2, … , 𝑛 } . Diambil sebarang titik yang bertetangga 𝑥, 𝑦 ∈ 𝑉(𝐺𝐨𝑆 𝑚 ) − 𝑊 , akibatnya 𝑥 = 𝑣 𝑖0 dan 𝑦 = 𝑣 𝑖𝑗 dengan 𝑗 = 2,3, … , 𝑚 . Oleh karena itu |{𝑣 𝑖0 , 𝑣 𝑖𝑗 } ∩ 𝑁(𝑣 𝑖1 )| = |{𝑣 𝑖0 }| = 1 .  Berdasarkan  uraian  diatas 𝑊 merupakan himpunan pembeda ketetanggaan lokal.
Selanjutnya  ditunjukkan  bahwa 𝑊 merupakan  himpunan  pembeda  ketetanggaan  lokal minimal.  Diambil  sebarang 𝑊 ′ ⊆ 𝑉(𝐺𝐨𝑆 𝑚 ) , |𝑊 ′ | < |𝑊| .  Terdapat  tiga  kemungkinan yaitu 𝑊 ′ ⊆ 𝐼 , 𝑊 ′ ⊆ ⋃ 𝑆 𝑚 𝑖 𝑛 𝑖=1 , atau 𝑊 ′ ⊆ 𝐵 ∪ 𝑃 , dengan 𝐵 ⊆ 𝐼 dan 𝑃 ⊆ ⋃ 𝑆 𝑚 𝑖 𝑛 𝑖=1 .
a. Untuk 𝑊 ′ ⊆ 𝐼 . Tanpa mengurangi keumuman bukti, misalkan 𝑣 11 ∉ 𝑊′ . Akibatntya terdapat  pasangan  titik  bertetangga 𝑣 10 , 𝑣 12 ∈ 𝑉(𝐺o𝑆 𝑚 ) − 𝑊′ .  Diambil  sebaranga 𝑣 𝑝1 ∈ 𝑊′ dengan (𝑣 𝑝1 , 𝑣 10 ) > 1 atau 𝑑(𝑣 𝑝1 , 𝑣 12 ) > 1 sehingga |{𝑣 10 , 𝑣 12 } ∩ 𝑁(𝑣 𝑝1 )| = 0 ≠ 1 . Berdasarkan Definisi himpunan pembeda ketetanggaan lokal 𝑊′ bukan himpunan pembeda ketetanggaan lokal.
b. Untuk 𝑊 ′ ⊆ ⋃ 𝑆 𝑚 𝑖 𝑛 𝑖=1 . Tanpa mengurangi keumuman bukti, misalkan 𝑣 1𝑝 ∉ 𝑊 ′ , 𝑝 ≠ 1 . Akibatnya terdapat pasangan titik bertetangga 𝑣 10 , 𝑣 12 ∈ 𝑉(𝐺o𝑆 𝑚 ) − 𝑊′ . Diambil sebarang 𝑣 𝑝𝑞 ∈ 𝑊 ′ dan 𝑝, 𝑞 ≠ 1 dengan (𝑣 𝑝𝑞 , 𝑣 10 ) > 1 atau 𝑑(𝑣 𝑝𝑞 , 𝑣 12 ) > 1 sehingga |{𝑣 10 , 𝑣 12 } ∩ 𝑁(𝑣 𝑝𝑞 )| = 0 ≠ 1 .  Berdasarkan  Definisi  himpunan  pembeda ketetanggaan lokal 𝑊′ bukan himpunan pembeda ketetanggaan lokal.
c. Sedangkan untuk 𝑊 ′ ⊆ 𝐵 ∪ 𝑃 , dengan 𝐵 ⊆ 𝐼 dan 𝑃 ⊆ ⋃ 𝑆 𝑚 𝑖 𝑛 𝑖=1 . Tanpa mengurangi keumuman bukti, misalkan 𝑣 1𝑝 ∉ 𝑊 ′ , 𝑝 ∈ {0,1, … , 𝑚} . Akibatnya terdapat pasangan titik  bertetangga 𝑣 1𝑥 , 𝑣 1𝑦 ∈ 𝑉(𝐺o𝑆 𝑚 ) − 𝑊 ′ ,  dengan 𝑥, 𝑦 ∈ {0,1, … , 𝑚}, 𝑥 ≠ 𝑦 . Diambil  sebarang 𝑣 𝑘𝑑 ∈ 𝑊 ′ , 𝑘 ≠ 1 dengan (𝑣 𝑘𝑑 , 𝑣 1𝑥 ) > 1 atau 𝑑(𝑣 𝑘𝑑 , 𝑣 1𝑦 ) > 1 sehingga |{𝑣 1𝑥 , 𝑣 1𝑦 } ∩ 𝑁(𝑣 𝑘𝑑 )| = 0 ≠ 1 . Berdasarkan Definisi himpunan pembeda ketetanggaan lokal 𝑊′ bukan himpunan pembeda ketetanggaan lokal.
Oleh karena itu 𝑊′ bukan himpunan pembeda ketetanggaan lokal. Jadi 𝑊 merupakan basis ketetanggaan lokal dan 𝑑𝑖𝑚 𝐴𝑙 (𝐺𝐨𝑆 𝑚 ) = |𝑉(𝐺)| ∎
Akibat 2.10. Misalkan 𝐺 graf terhubung berordo 𝑛 ≥ 2 , graf 𝑆 𝑚 berordo 𝑚 ≥ 2 , dan titik cangkok 𝑜 bukan merupakan titik dominasi pada graf 𝑆 𝑚 . Jika Jika 𝑘 ≥ 1 maka
𝑑𝑖𝑚 𝐴𝐿 (𝐺𝐨 𝑘 𝑆 𝑚 ) = |𝑉(𝐺𝐨 𝑘−1 𝑆 𝑚 )|
Bukti. Misalkan 𝐺 ′ = 𝐺𝐨 𝑘−1 𝑆 𝑚 , akibatnya 𝐺𝐨 𝑘 𝑆 𝑚 =  𝐺′𝐨𝑆 𝑚 . Bedasarkan Teorema 2.9, diperoleh 𝑑𝑖𝑚 𝐴𝑙 (𝐺𝐨 𝑘 𝑆 𝑚 ) = |𝑉(𝐺𝐨 𝑘−1 𝑆 𝑚 )| . ∎
Teorema 2.11. Misalkan 𝐺 adalah graf terhubung berordo 𝑛 ≥ 2 dan 𝐻 adalah barisan 𝑛 graf 𝑆 𝑚 berordo 𝑚 ≥ 2 . Jika titik cangkok 𝑜 bukan merupakan titik dominan dari graf bintang 𝑆 𝑚 dan 𝑘 ≥ 1 maka
𝑑𝑖𝑚 𝐴𝐿 (𝐺𝐨 𝒌 𝑆 𝑚 ) = |𝑉(𝐺)|
Bukti. Misalkan 𝑊 = 𝐼 = {𝑣 𝑖01 |𝑖 = 1,2, … , 𝑛 } .  Diambil  sebarang  titik  yang bertetangga 𝑥, 𝑦 ∈ 𝑉(𝐺𝐨 𝒌 𝑆 𝑚 ) − 𝑊 ,  akibatnya 𝑥 = 𝑣 𝑖𝑡0 dan 𝑦 = 𝑣 𝑖𝑡𝑗 dengan 𝑗 = 2,3, … , 𝑚 .  Oleh  karena  itu |{𝑣 𝑖𝑡0 , 𝑣 𝑖𝑡𝑗 } ∩ 𝑁(𝑣 𝑖01 )| = |{𝑣 𝑖𝑡0 }| = 1 .  Berdasarkan  uraian diatas 𝑊 merupakan himpunan pembeda ketetanggaan lokal.
Selanjutnya  ditunjukkan  bahwa 𝑊 merupakan  basis  ketetanggaan  lokal.  Diambil sebarang 𝑊 ′ ⊆ 𝑉(𝐺𝐨 𝒌 𝑆 𝑚 ) , |𝑊 ′ | < |𝑊| .  Terdapat  tiga  kemungkinan  yaitu 𝑊 ′ ⊆ 𝐼 , 𝑊 ′ ⊆ ⋃ 𝑆 𝑚 𝑖𝑡 𝑛𝑘 𝑖=1 , atau 𝑊 ′ ⊆ 𝐵 ∪ 𝑃 , dengan 𝐵 ⊆ 𝐼 dan 𝑃 ⊆ ⋃ 𝑆 𝑚 𝑖𝑡 𝑛𝑘 𝑖=1 . a. Untuk 𝑊 ′ ⊆ 𝐼 . Tanpa mengurangi keumuman bukti, misalkan 𝑣 101 ∉ 𝑊′ . Akibatntya terdapat pasangan titik bertetangga 𝑣 1𝑡0 , 𝑣 1𝑡2 ∈ 𝑉(𝐺𝐨 𝒌 𝑆 𝑚 ) − 𝑊′ . Diambil sebaranga 𝑣 𝑝01 ∈ 𝑊′ dengan (𝑣 𝑝01 , 𝑣 1𝑡0 ) > 1 atau 𝑑(𝑣 𝑝01 , 𝑣 1𝑡2 ) > 1 sehingga |{𝑣 1𝑡0 , 𝑣 1𝑡2 } ∩ 𝑁(𝑣 𝑝01 )| = 0 ≠ 1 . Berdasarkan Definisi himpunan pembeda ketetanggaan lokal 𝑊′ bukan himpunan pembeda ketetanggaan lokal.
b. Untuk 𝑊 ′ ⊆ ⋃ 𝑆 𝑚 𝑖𝑡 𝑛𝑘 𝑖=1 Tanpa mengurangi keumuman bukti, misalkan 𝑣 11𝑝 ∉ 𝑊 ′ , 𝑝 ≠ 1 .  Akibatnya  terdapat  pasangan  titik  bertetangga 𝑣 110 , 𝑣 112 ∈ 𝑉(𝐺𝐨 𝒌 𝑆 𝑚 ) − 𝑊′ . Diambil  sebarang 𝑣 𝑝𝑡𝑞 ∈ 𝑊 ′ dan 𝑝, 𝑞 ≠ 1 dengan (𝑣 𝑝𝑡𝑞 , 𝑣 110 ) > 1 atau 𝑑(𝑣 𝑝𝑡𝑞 , 𝑣 112 ) > 1 sehingga |{𝑣 110 , 𝑣 112 } ∩ 𝑁(𝑣 𝑝𝑡𝑞 )| = 0 ≠ 1 . Berdasarkan Definisi himpunan pembeda ketetanggaan lokal 𝑊′ bukan himpunan pembeda ketetanggaan lokal.
c. Sedangkan untuk 𝑊 ′ ⊆ 𝐵 ∪ 𝑃 , dengan 𝐵 ⊆ 𝐼 dan 𝑃 ⊆ ⋃ 𝑆 𝑚 𝑖𝑡 𝑛𝑘 𝑖=1 . Tanpa mengurangi keumuman bukti, misalkan 𝑣 1𝑡𝑝 ∉ 𝑊 ′ , 𝑝 ∈ {0,1, … , 𝑚} . Akibatnya terdapat pasangan titik  bertetangga 𝑣 1𝑡𝑥 , 𝑣 1𝑡𝑦 ∈ 𝑉(𝐺o𝑆 𝑚 ) − 𝑊 ′ ,  dengan 𝑥, 𝑦 ∈ {0,1, … , 𝑚}, 𝑥 ≠ 𝑦 . Diambil  sebarang 𝑣 𝑘𝑡𝑑 ∈ 𝑊 ′ , 𝑘 ≠ 1, 𝑑 ∈ {0,1, … , 𝑚} dengan (𝑣 𝑘𝑡𝑑 , 𝑣 1𝑡𝑥 ) > 1 atau 𝑑(𝑣 𝑘𝑡𝑑 , 𝑣 1𝑡𝑦 ) > 1 sehingga |{𝑣 1𝑡𝑥 , 𝑣 1𝑡𝑦 } ∩ 𝑁(𝑣 𝑘𝑡𝑑 )| = 0 ≠ 1 . Berdasarkan Definisi himpunan pembeda ketetanggaan lokal 𝑊′ bukan himpunan pembeda ketetanggaan lokal.
Oleh karena itu, 𝑊′ bukan himpunan pembeda ketetanggaan lokal. Jadi 𝑊 merupakan basis ketetanggaan lokal dari graf 𝐺𝐨 𝒌 𝑆 𝑚 dan 𝑑𝑖𝑚 𝐴𝑙 (𝐺𝐨 𝒌 𝑆 𝑚 ) = |𝑉(𝐺)| ∎
Teorema 2.12. Misalkan 𝐺 merupakan graf 𝐶 𝑛 , graf 𝑆 𝑛 , graf 𝐾 𝑛 , atau graf 𝑃 𝑛 berordo 𝑛 ≥ 2 dan 𝑚 ≥ 4 . Jika 𝛾(𝐺) merupakan bilangan dominasi pada graf 𝐺 maka
𝑑𝑖𝑚 𝐴𝐿 (𝐺𝐨𝐶 𝑚 ) = { |𝑉(𝐺)|(𝑑𝑖𝑚 𝐴𝐿 (𝐶 𝑚 ) − 1) + 𝑉(𝐺), untuk 𝑚 = 4𝑘 atau 𝑚 = 4𝑘 + 3 |𝑉(𝐺)|(𝑑𝑖𝑚 𝐴𝐿 (𝐶 𝑚 ) − 1) + 𝛾(𝐺), untuk 𝑚 yang lain dengan 𝑘 ∈ ℕ .
Bukti. Misalkan 𝐺 merupakan graf 𝐶 𝑛 , graf 𝑆 𝑛 , graf 𝐾 𝑛 , atau graf 𝑃 𝑛 berordo 𝑛 ≥ 2 . 𝑆 ⊆ 𝑉(𝐺) dan 𝑆 = {𝑣 𝑛1 , 𝑣 𝑛2 , … , 𝑣 𝑛𝛾(𝐺) } merupakan himpunan dominasi minimal dari graf 𝐺 , selanjutnya  berdasarkan  penamaan  titik  pada  graf  hasil  operasi  kali  comb  himpunan 𝑆 pada 𝐺𝐨𝐶 𝑚 adalah 𝑆 ∗ = {𝑣 𝑛 1 1 , 𝑣 𝑛 2 1 , … , 𝑣 𝑛 𝛾(𝐺) 1 } . Berdasarkan Teorema 2.3,
𝐵 𝑖 = {𝑣 𝑖1 , 𝑣 𝑖5 , … , 𝑣 𝑖4(𝑘−1)+1 , … , 𝑣 𝑖[4(⌈ 𝑚 4 ⌉−1)+1] |𝑘 ≤ ⌈ 𝑚 4 ⌉} , dengan 𝑖 = 1,2, … , 𝑛 merupakan basis ketetanggaan lokal graf 𝐶 𝑚 𝑖 . Terdapat empat kemungkinan nilai 𝑚 yaitu 𝑚 = 4𝑘, 𝑚 = 4𝑘 + 1, 𝑚 = 4𝑘 + 2, atau 𝑚 = 4𝑘 + 3.
a. Untuk 𝑚 = 4𝑘 atau 𝑚 = 4𝑘 + 3 .  Dipilih 𝑊 = ⋃ 𝐵 𝑖 𝑛 𝑖=1 .  Diambil  sepasang  titik bertetangga 𝑥, 𝑦 ∈ 𝑉(𝐺𝐨𝐶 𝑚 ) − 𝑊 ,  akibatnya 𝑥, 𝑦 ∈ 𝐶 𝑚 𝑖 − 𝐵 𝑖 .  Karena 𝐼 ⊆ 𝑊 maka berdasarkan  Teorema  2.2, 𝑊 merupakan  himpunan  pembeda  ketetanggaan  lokal. Karena 𝐵 𝑖 merupakan basis ketetanggaan lokal dari 𝐶 𝑚 , maka 𝑊 merupakan basis ketetanggaan lokal dari graf 𝐺𝐨𝐶 𝑚 .
b. Sedangkan  untuk 𝑚 = 4𝑘 + 1 atau 𝑚 = 4𝑘 + 2 .  Misalkan 𝑊 = 𝑆 ∗ ⋃ {𝑣 𝑖4(𝑘−1) } 𝑛 𝑖=1 dengan 𝑘 = 2,3, … , ⌈ 𝑚 4 ⌉ . Diambil sebarang titik yang bertetangga 𝑥, 𝑦 ∈ 𝑉(𝐺𝐨𝐶 𝑚 ) − 𝑊 , terdapat dua kasus yaitu 𝑥, 𝑦 ∈ 𝐼 − 𝑆 ∗ atau 𝑥 ∈ 𝐼 − 𝑆 ∗ dan 𝑦 ∈ 𝐶 𝑚 𝑖 − {𝑣 𝑖4(𝑘−1) } . (i) Untuk 𝑥, 𝑦 ∈ 𝐼 − 𝑆 ∗ , 𝑥 = 𝑣 𝑟1 dan 𝑦 = 𝑣 𝑘1 dengan 𝑟, 𝑘 ≠ 𝑛 𝑖 , 𝑖 = 1,2, … , 𝛾(𝐺) . Dipilih 𝑣 𝑖1 ∈ 𝐼 dengan 𝑑(𝑣 𝑖1 , 𝑣 𝑟1 ) = 1 atau 𝑑(𝑣 𝑖1 , 𝑣 𝑘1 ) > 1 .  Oleh  karena  itu |𝑁(𝑣 𝑖1 ) ∩ {𝑣 𝑟1 , 𝑣 𝑘1 }| = |{𝑣 𝑟1 }| = 1 .
(ii) Untuk 𝑥 ∈ 𝐼 − 𝑆 ∗ dan 𝑦 ∈ 𝐶 𝑚 𝑖 − {𝑣 𝑖4(𝑘−1) } ,  akibatnya 𝑥 = 𝑣 𝑟1 𝑑𝑎𝑛 𝑦 = 𝑣 𝑟2 dengan 𝑟 ≠ 𝑛 𝑖 , 𝑖 = 1,2, … , 𝛾(𝐺) .  Karena 𝑆 ∗ merupakan  himpunan  dominasi minimal  dari  induk,  maka  terdapat 𝑣 𝑛 𝑘 1 ∈ 𝑆 ∗ .  Karena 𝑑(𝑣 𝑟1 , 𝑣 𝑛 𝑘 1 ) = 1 dan 𝑑(𝑣 𝑟2 , 𝑣 𝑛 𝑘 1 ) > 1 maka |𝑁(𝑣 𝑛 𝑘 1 ) ∩ {𝑣 𝑟1 , 𝑣 𝑟2 }| = |{𝑣 𝑟1 }| = 1 .
Berdasarkan uraian diatas maka 𝑊 merupakan himpunan pembeda ketetanggaan lokal. Selanjutnya  akan  ditunjukkan  bahwa 𝑊 merupakan  basis  ketetanggaan  lokal.  Diambil sebarang 𝑊 ′ ⊆ 𝑉(𝐺𝐨𝐶 𝑚 ) , |𝑊 ′ | < |𝑊| . Terdapat empat kemungkinan nilai 𝑚 yaitu 𝑚 = 4𝑘, 𝑚 = 4𝑘 + 1, 𝑚 = 4𝑘 + 2, atau 𝑚 = 4𝑘 + 3.
a. Untuk 𝑚 = 4𝑘 atau 𝑚 = 4𝑘 + 3 .  Karena |𝑊 ′ | < |𝑊| dan |𝑊 ′ | < |⋃ 𝐵 𝑖 𝑛 𝑖=1 | , akibatnya  terdapat 𝐶 𝑚 𝑖 sehingga  maksimal  terdapat |𝐵 𝑖 | − 1 titik  yang  menjadi anggota 𝑊 ′ . Tanpa mengurangi keumuman bukti, misalkan 𝑖 = 1 sehingga maksimal terdapat |𝐵 1 | − 1 titik  yang  menjadi  anggota 𝑊 ′ .  Akibatnya 𝑣 1𝑟 , 𝑣 1ℎ ∈ 𝑊 ′ , 𝑟 ≠ ℎ , dan 𝑙(𝑣 1𝑟 − 𝑣 1ℎ ) > 4 .  Berdasarkan  Lema  4.1.1, 𝑊 ′ bukan  merupakan  himpunan pembeda ketetanggaan lokal.
b. Sedangkan  untuk 𝑚 = 4𝑘 + 1 atau 𝑚 = 4𝑘 + 2 .  Terdapat  dua  kemungkinan  yaitu 𝑊 ′ = 𝐼′ ⋃ 𝐻′ 𝑛 𝑖=1 dengan 𝐼 ′ ⊆ 𝐼 , |𝐼′| < 𝛾(𝐺) , dan |𝐻′| = |⋃ {𝑣 𝑖4(𝑘−1) } 𝑛 𝑖=1 | dengan 𝑘 = 2,3, … , ⌈ 𝑚 4 ⌉ atau 𝑊 ′ = 𝐼′ ⋃ 𝐻′ 𝑛 𝑖=1 dengan |𝐼′| = 𝛾(𝐺), 𝐻′ ⊆ ⋃ 𝐶 𝑚 𝑖 𝑛 𝑖=1 ,  dan |𝐻′| < |⋃ {𝑣 𝑖4(𝑘−1) } 𝑛 𝑖=1 | .
i. Untuk 𝑊 ′ = 𝐼′ ⋃ 𝐻′ 𝑛 𝑖=1 dengan 𝐼 ′ ⊆ 𝐼 , |𝐼′| < 𝛾(𝐺) , dan |𝐻′| = |⋃ {𝑣 𝑖4(𝑘−1) } 𝑛 𝑖=1 | dengan 𝑘 = 2,3, … , ⌈ 𝑚 4 ⌉ .  Karena 𝐼 ′ bukan  merupakan  himpunan  dominasi
minimal, maka terdapat titik 𝑣 𝑟1 ∈ 𝐼 − 𝐼 ′ sehingga 𝑑(𝑣 𝑟1 , 𝑣 𝑛 𝑘 1 ) > 1, 𝑣 𝑛 𝑘 1 ∈ 𝐼 ′ . Terdapat  pasangan  titik  bertetangga 𝑣 𝑟𝑝 , 𝑣 𝑟𝑞 ∈ 𝑊′ dengan 𝑝 ≠ 𝑞 .  Diambil sebarang 𝑥 ∈ 𝑊 ′ ,  maka  terdapat  dua  kemungkinan  yaitu 𝑥 = 𝑣 𝑛 𝑘 1 , 𝑣 𝑛 𝑘 1 ∈ 𝐼 ′
atau 𝑥 = 𝑣 𝑖ℎ dengan ℎ ≠ 1, 𝑣 𝑖ℎ ∈ 𝐻 ′ .  Jika 𝑥 = 𝑣 𝑛 𝑘 1 maka 𝑣 𝑟𝑝 , 𝑣 𝑟𝑞 ∉ 𝑁(𝑥) . Sedangkan  jika 𝑥 = 𝑣 𝑣 𝑖ℎ maka 𝑣 𝑟𝑝 , 𝑣 𝑟𝑞 ∉ 𝑁(𝑥) .  Akibatnya |{𝑣 𝑟𝑝 , 𝑣 𝑟𝑞 } ∩ 𝑁(𝑥)| ≠ 1 .
ii. Selanjutnya  untuk 𝑊 ′ = 𝐼′ ⋃ 𝐻′ 𝑛 𝑖=1 dengan |𝐼′| = 𝛾(𝐺), 𝐻′ ⊆ ⋃ 𝐶 𝑚 𝑖 𝑛 𝑖=1 ,  dan |𝐻′| < |⋃ {𝑣 𝑖4(𝑘−1) } 𝑛 𝑖=1 | dengan 𝑘 = 2,3, … , ⌈ 𝑚 4 ⌉ .  Terdapat 𝐶 𝑚 𝑖 sehingga maksimal  terdapat |{𝑣 𝑖4(𝑘−1) }| − 1 titik  yang  menjadi  anggota 𝑊 ′ .  Tanpa mengurangi  keumuman  bukti,  misalkan 𝑖 = 1 sehingga  maksimal  terdapat (|𝑣 14(𝑘−1) | − 1) titik  yang  menjadi  anggota 𝑊 ′ .  Akibatnya  terdapat  pasangan titik  bertetangga 𝑣 1𝑝 , 𝑣 1𝑞 ∈ 𝑊′ dengan 𝑝 ≠ 𝑞 dan 𝑙(𝑣 1𝑝 − 𝑣 1𝑞 ) > 4 . Berdasarkan Lema 2.1 𝑊 ′ bukan himpunan pembeda ketetanggaan lokal.
Berdasarkan uraian diatas 𝑊′ bukan himpunan pembeda ketetanggaan lokal. Oleh karena  itu 𝑊 merupakan  basis  ketetanggaan  lokal  dan 𝑑𝑖𝑚 𝐴𝐿 (𝐺𝐨𝐶 𝑚 ) = { |𝑉(𝐺)|(𝑑𝑖𝑚 𝐴𝐿 (𝐶 𝑚 ) − 1) + 𝑉(𝐺), untuk 𝑚 = 4𝑘 atau 𝑚 = 4𝑘 + 3 |𝑉(𝐺)|(𝑑𝑖𝑚 𝐴𝐿 (𝐶 𝑚 ) − 1) + 𝛾(𝐺), untuk 𝑚 yang lain
∎
Akibat 2.13. Misalkan 𝐺 merupakan graf 𝐶 𝑛 , graf 𝑆 𝑛 , graf 𝐾 𝑛 , atau graf 𝑃 𝑛 berordo 𝑛 ≥ 2 dan 𝑚 ≥ 4 . Jika 𝑘 ≥ 1 maka
𝑑𝑖𝑚 𝐴𝐿 (𝐺𝐨 𝑘 𝐶 𝑚 )
= { |𝑉(𝐺𝐨 𝑘−1 𝐶 𝑚 )|(𝑑𝑖𝑚 𝐴𝐿 (𝐶 𝑚 ) − 1) + 𝑉(𝐺𝐨 𝑘−1 𝐶 𝑚 ), untuk 𝑚 = 4𝑘 atau 𝑚 = 4𝑘 + 3 |𝑉(𝐺𝐨 𝑘−1 𝐶 𝑚 )|(𝑑𝑖𝑚 𝐴𝐿 (𝐶 𝑚 ) − 1) + 𝛾(𝐺𝐨 𝑘−1 𝐶 𝑚 ), untuk 𝑚 yang lain
Bukti. Misalkan 𝐺 ′ = 𝐺𝐨 𝑘−1 𝐶 𝑚 ,  akibatnya 𝐺𝐨 𝑘 𝐶 𝑚 =  𝐺′𝐨𝐶 𝑚 .  Bedasarkan  Teorema
2.12, diperoleh 𝑑𝑖𝑚 𝐴𝐿 (𝐺𝐨 𝑘 𝐶 𝑚 ) = { |𝑉(𝐺𝐨 𝑘−1 𝐶 𝑚 )|(𝑑𝑖𝑚 𝐴𝐿 (𝐶 𝑚 ) − 1) + 𝑉(𝐺𝐨 𝑘−1 𝐶 𝑚 ), untuk 𝑚 = 4𝑘 atau 𝑚 = 4𝑘 + 3 |𝑉(𝐺𝐨 𝑘−1 𝐶 𝑚 )|(𝑑𝑖𝑚 𝐴𝐿 (𝐶 𝑚 ) − 1) + 𝛾(𝐺𝐨 𝑘−1 𝐶 𝑚 ), 𝑢𝑛𝑡𝑢𝑘 𝑚 yang lain ∎
Teorema 2.14. Misalkan 𝐺 merupakan graf 𝐶 𝑛 , graf 𝑆 𝑛 , graf 𝐾 𝑛 , dan graf 𝑃 𝑛 berordo 𝑛 ≥ 2 dan 𝑚 ≥ 4 . Jika 𝛾(𝐺) merupakan bilangan dominasi dari graf 𝐺 dan 𝑘 ≥ 1 maka 𝑑𝑖𝑚 𝐴𝐿 (𝐺𝐨 𝒌 𝐶 𝑚 ) =
{ 𝑘|𝑉(𝐺)|(𝑑𝑖𝑚 𝐴𝐿 (𝐶 𝑚 ) − 1) + 𝑉(𝐺), untuk 𝑚 = 4𝑘 atau 𝑚 = 4𝑘 + 3 𝑘|𝑉(𝐺)|(𝑑𝑖𝑚 𝐴𝐿 (𝐶 𝑚 ) − 1) + 𝛾(𝐺), untuk 𝑚 yang lain
dengan 𝑘 ∈ ℕ .
Bukti. Misalkan 𝐺 merupakan graf 𝐶 𝑛 , graf 𝑆 𝑛 , graf 𝐾 𝑛 , dan graf 𝑃 𝑛 berordo 𝑛 ≥ 2 . 𝑆 ⊆ 𝑉(𝐺) dan 𝑆 = {𝑣 𝑛1 , 𝑣 𝑛2 , … , 𝑣 𝑛𝛾(𝐺) } merupakan himpunan dominasi minimal dari graf 𝐺 , selanjutnya  berdasarkan  penamaan  titik  pada  graf  hasil  operasi  kali  comb  himpunan 𝑆 pada 𝐺𝐨 𝒌 𝐶 𝑚 adalah 𝑆 ∗ = {𝑣 𝑛 1 01 , 𝑣 𝑛 2 01 , … , 𝑣 𝑛 𝛾(𝐺) 01 } . Berdasarkan Teorema 2.3
𝐵 𝑖𝑡 = {𝑣 𝑖01 , 𝑣 𝑖𝑡5 , … , 𝑣 𝑖𝑡4(𝑘−1)+1 , … , 𝑣 𝑖𝑡[4(⌈ 𝑚 4 ⌉−1)+1] |𝑘 ≤ ⌈ 𝑚 4 ⌉} , dengan 𝑖 = 1,2, … , 𝑛 merupakan basis ketetanggaan lokal graf 𝐶 𝑚 𝑖𝑡 . Terdapat empat kemungkinan nilai 𝑚 yaitu 𝑚 = 4𝑘, 𝑚 = 4𝑘 + 1, 𝑚 = 4𝑘 + 2, atau 𝑚 = 4𝑘 + 3.
a. Untuk 𝑚 = 4𝑘 atau 𝑚 = 4𝑘 + 3 .  Dipilih 𝑊 = ⋃ 𝐵 𝑖𝑡 𝑛𝑘 𝑖=1 .  Diambil  sepasang  titik bertetangga 𝑥, 𝑦 ∈ 𝑉(𝐺𝐨 𝒌 𝐶 𝑚 ) − 𝑊 , akibatnya 𝑥, 𝑦 ∈ 𝐶 𝑚 𝑖𝑡 − 𝐵 𝑖𝑡 . Karena 𝐼 ⊆ 𝑊 maka berdasarkan  Teorema  2.2, 𝑊 merupakan  himpunan  pembeda  ketetanggaan  lokal. Karena 𝐵 𝑖𝑡 merupakan basis ketetanggaan lokal dari 𝐶 𝑚 , maka 𝑊 merupakan basis ketetanggaan lokal dari graf 𝐺𝐨 𝒌 𝐶 𝑚 . b. Sedangkan untuk 𝑚 = 4𝑘 + 1 atau 𝑚 = 4𝑘 + 2 . Misalkan 𝑊 = 𝑆 ∗ ⋃ {𝑣 𝑖𝑡4(𝑟−1) } 𝑛𝑘 𝑖=1
dengan 𝑟 = 2,3, … , ⌈ 𝑚 4 ⌉ . Diambil sepasang titik bertetangga 𝑥, 𝑦 ∈ 𝑉(𝐺𝐨 𝒌 𝐶 𝑚 ) − 𝑊 , terdapat dua kasus yaitu 𝑥, 𝑦 ∈ 𝐼 − 𝑆 ∗ atau 𝑥 ∈ 𝐼 − 𝑆 ∗ dan 𝑦 ∈ 𝐶 𝑚 𝑖𝑡 − {𝑣 𝑖𝑡4(𝑘−1) } . (i) Untuk 𝑥, 𝑦 ∈ 𝐼 − 𝑆 ∗ , 𝑥 = 𝑣 𝑟01 dan 𝑦 = 𝑣 𝑘01 dengan 𝑟, 𝑘 ≠ 𝑛 𝑖 , 𝑖 = 1,2, … , 𝛾(𝐺) . Dipilih 𝑣 𝑖01 ∈ 𝐼 dengan 𝑑(𝑣 𝑖01 , 𝑣 𝑟01 ) = 1 atau 𝑑(𝑣 𝑖01 , 𝑣 𝑘01 ) > 1 .  Oleh  karena  itu |𝑁(𝑣 𝑖01 ) ∩ {𝑣 𝑟01 , 𝑣 𝑘01 }| = |{𝑣 𝑟01 }| = 1
.
(ii) Untuk 𝑥 ∈ 𝐼 − 𝑆 ∗ dan 𝑦 ∈ 𝐶 𝑚 𝑖𝑡 − {𝑣 𝑖𝑡4(𝑘−1) } ,  akibatnya 𝑥 = 𝑣 𝑟01 𝑑𝑎𝑛 𝑦 = 𝑣 𝑟𝑡2 dengan 𝑟 ≠ 𝑛 𝑖 , 𝑖 = 1,2, … , 𝛾(𝐺) .  Karena 𝑆 ∗ merupakan  himpunan  dominasi  dari induk, maka terdapat 𝑣 𝑛 𝑘 01 ∈ 𝑆 ∗ . Karena 𝑑(𝑣 𝑟01 , 𝑣 𝑛 𝑘 01 ) = 1 dan 𝑑(𝑣 𝑟𝑡2 , 𝑣 𝑛 𝑘 01 ) > 1 maka |𝑁(𝑣 𝑛 𝑘 01 ) ∩ {𝑣 𝑟01 , 𝑣 𝑟𝑡2 }| = |{𝑣 𝑟01 }| = 1 .
Berdasarkan uraian diatas maka 𝑊 merupakan himpunan pembeda ketetanggaan lokal. Selanjutnya  akan  ditunjukkan  bahwa 𝑊 merupakan  basis  ketetanggaan  lokal  minimal. Diambil sebarang 𝑊 ′ ⊆ 𝑉(𝐺𝐨 𝒌 𝐶 𝑚 ) , |𝑊 ′ | < |𝑊| . Terdapat empat kemungkinan nilai 𝑚 yaitu 𝑚 = 4𝑘, 𝑚 = 4𝑘 + 1, 𝑚 = 4𝑘 + 2, atau 𝑚 = 4𝑘 + 3.
a. Untuk 𝑚 = 4𝑘 atau 𝑚 = 4𝑘 + 3 .  Karena |𝑊 ′ | < |𝑊| dan |𝑊 ′ | < |⋃ 𝐵 𝑖𝑡 𝑛𝑘 𝑖=1 | , akibatnya  terdapat 𝐶 𝑚 𝑖𝑡 sehingga  maksimal  terdapat |𝐵 𝑖𝑡 | − 1 titik  yang  menjadi anggota 𝑊 ′ . Tanpa mengurangi keumuman bukti, misalkan 𝑖 = 1 dan 𝑡 = 1 sehingga maksimal terdapat (|𝐵 11 | − 1) titik yang menjadi anggota 𝑊 ′ . Akibatnya 𝑣 1𝑡𝑟 , 𝑣 1𝑡ℎ ∈ 𝑊 ′ , 𝑟 ≠ ℎ ,  dan 𝑙(𝑣 1𝑡𝑟 − 𝑣 1𝑡ℎ ) > 4 .  Berdasarkan  Lema  2.1, 𝑊 ′ bukan  merupakan himpunan pembeda ketetanggaan lokal.
b. Sedangkan  untuk 𝑚 = 4𝑘 + 1 atau 𝑚 = 4𝑘 + 2 .  Terdapat  dua  kemungkinan  yaitu 𝑊 ′ = 𝐼′ ⋃ 𝐻′ 𝑛𝑘 𝑖=1 dengan 𝐼 ′ ⊆ 𝐼 , |𝐼′| < 𝛾(𝐺) , dan |𝐻′| = |⋃ {𝑣 𝑖4(𝑟−1) } 𝑛𝑘 𝑖=1 | dengan 𝑟 =
2,3, … , ⌈ 𝑚 4 ⌉ atau 𝑊 ′ = 𝐼′ ⋃ 𝐻′ 𝑛𝑘 𝑖=1 dengan |𝐼′| = 𝛾(𝐺), 𝐻′ ⊆ ⋃ 𝐶 𝑚 𝑖𝑡 𝑛𝑘 𝑖=1 ,  dan |𝐻′| < |⋃ {𝑣 𝑖4(𝑟−1) } 𝑛𝑘 𝑖=1 | .
i. Untuk 𝑊 ′ = 𝐼′ ⋃ 𝐻′ 𝑛𝑘 𝑖=1 dengan 𝐼 ′ ⊆ 𝐼 , |𝐼′| < 𝛾(𝐺) , dan |𝐻′| = |⋃ {𝑣 𝑖4(𝑟−1) } 𝑛𝑘 𝑖=1 |
dengan 𝑟 = 2,3, … , ⌈ 𝑚 4 ⌉ .  Karena 𝐼 ′ bukan  merupakan  himpunan  dominasi minimal,  maka  terdapat  titik 𝑣 ℎ01 ∈ 𝐼 − 𝐼 ′ sehingga 𝑑(𝑣 ℎ01 , 𝑣 𝑛 𝑘 01 ) > 1, 𝑣 𝑛 𝑘 01 ∈ 𝐼 ′ .  Terdapat  pasangan  titik  bertetangga (𝑣 ℎ𝑡𝑝 , 𝑣 ℎ𝑡𝑞 ) ∈ 𝑉(𝐺𝐨𝐶 𝑚 ) − 𝑊′ dengan 𝑝 ≠ 𝑞 . Diambil sebarang 𝑥 ∈ 𝑊 ′ , maka terdapat dua kemungkinan yaitu 𝑥 = 𝑣 𝑛 𝑘 01 , 𝑣 𝑛 𝑘0 1 ∈ 𝐼 ′ atau 𝑥 = 𝑣 𝑖𝑡𝑦 dengan 𝑦 ≠ 1, 𝑣 𝑖𝑦 ∈ 𝐻 ′ .  Jika 𝑥 = 𝑣 𝑛 𝑘 01 maka 𝑣 ℎ𝑡𝑝 , 𝑣 ℎ𝑡𝑞 ∉ 𝑁(𝑥) .  Sedangkan  jika 𝑥 = 𝑣 𝑣 𝑖𝑡𝑦 maka 𝑣 ℎ𝑡𝑝 , 𝑣 ℎ𝑡𝑞 ∉ 𝑁(𝑥) . Akibatnya |{𝑣 ℎ𝑡𝑝 , 𝑣 ℎ𝑡𝑞 } ∩ 𝑁(𝑥)| ≠ 1 ii. Selanjutnya  untuk 𝑊 ′ = 𝐼′ ⋃ 𝐻′ 𝑛 𝑖=1 dengan |𝐼′| = 𝛾(𝐺), 𝐻′ ⊆ ⋃ 𝐶 𝑚 𝑖𝑡 𝑛𝑘 𝑖=1 ,  dan |𝐻′| < |⋃ {𝑣 𝑖4(𝑟−1) } 𝑛𝑘 𝑖=1 | dengan 𝑟 = 2,3, … , ⌈ 𝑚 4 ⌉ .  Terdapat 𝐶 𝑚 𝑖𝑡 sehingga maksimal  terdapat |{𝑣 𝑖4(𝑟−1) }| − 1 titik  yang  menjadi  anggota 𝑊 ′ .  Tanpa mengurangi  keumuman  bukti,  misalkan 𝑖 = 1 sehingga  maksimal  terdapat (|𝑣 14(𝑟−1) | − 1) titik yang menjadi anggota 𝑊 ′ . Akibatnya terdapat pasangan titik  bertetangga 𝑣 1𝑡𝑝 , 𝑣 1𝑡𝑞 ∈ 𝑊′ dengan 𝑝 ≠ 𝑞 dan 𝑙(𝑣 1𝑡𝑝 − 𝑣 1𝑡𝑞 ) > 4 . Berdasarkan Lema 2.1, 𝑊 ′ bukan himpunan pembeda ketetanggaan lokal. Berdasarkan uraian diatas 𝑊′ bukan himpunan pembeda ketetanggaan lokal. Oleh karena itu 𝑊 merupakan basis ketetanggaan lokal dan 𝑑𝑖𝑚 𝐴𝐿 (𝐺𝐨 𝒌 𝐶 𝑚 ) = { 𝑘|𝑉(𝐺)|(𝑑𝑖𝑚 𝐴𝐿 (𝐶 𝑚 ) − 1) + 𝑉(𝐺), untuk 𝑚 = 4𝑘 antau 𝑚 = 4𝑘 + 3 𝑘|𝑉(𝐺)|(𝑑𝑖𝑚 𝐴𝐿 (𝐶 𝑚 ) − 1) + 𝛾(𝐺), untuk 𝑚 yang lain ∎

## 3 Daftar Pustaka
[1] Iswadi,  H.,  Baskoro,  E.T.,  Simanjutak,  R.,  2011, On  The  Metric  Dimension  of Corona  Product  Graphs , Far East  Journal  of Mathematical  Sciences (FJMS), 52 (2): 155-170.
[2] Okamoto, F., Crosse, L., Phinezy, B., Zhang, P., dan Kalamazo, 2010, The Local Metrik Dimension of Graph, Mathematica Bohemica, 135(3): 239-255.
[3] Jannesari, M. dan Omoomi, B., 2012, The Metrik Dimension of The Lexicographic Product of Graphs, Discrete Mathematics, Vol. 312, No. 22, pp. 3349-3356.
[4] Rodriguez-Velazquez,  Gomez.  C.G.,  dan  Barragan  –Ramirez,  G.  A.,  2014, Computing the Local Metric Dimension of Graph from The Local Metric Dimension of Primary Subgraph, arvix: 1402.0177v1[math.CO], 2 Februari 2014.
[5]   Rodriguez-Velazquez,  J.  A.  dan  Fernau,  H.,  2016, On  the  (Adjacency)  Metrik Dimension  of  Corona  and  Strong  Product  Graphs  and  Their  Local  Variants : Combinatorial and Computational Results.
[6] Susilowati, L., Salamin, Utoyo, M. I. dan Estuningsih, N., 2016, The Similarity of Metric Dimension and Local Metric Dimension of Rooted Product Graph, Far East Journal of Mathematical Sciences (FJMS), Volume 97, Number 7, Pages 841-856.
[7] Saputro,  S.  W.,  Mardina,  N.,  dan  Purwasi,  LA.,  2013, The  Metrik  Dimension  of Comb  Product  Graph, Graph  Theory  Conferience  in  Honor  of  Egawa’s  60 th Birthday.
[8] Susilowati,  L.  dan  Utoyo,  M.  I.,  2016, On  Comutative  Characterization  of Generalized Comb and Corona Products of Graph with Respect to the Local Metric Dimension , Far East Journal of Mathematical Sciences (FJMS), Volume 100.
[9] Munawwaroh, Ana Zahrotul, 2016, Dimensi Metrik Fraksional Generalisasi Hasil Kali Comb dari Graf Lengkap, Repository Unair.