Dimensi Metrik Lokal dari Hasil Perkalian Kuat Graf Bintang

Abstract

Diberikan graf terhubung dan sederhana G=(V(G), E(G)). Titik v elemen dari V(G) disebut membedakan titik x, y elemen V(G) jika jarak titik dari v ke x berbeda terhadap jarak titik v ke y. Himpunan  W subset V(G) dengan W= {w₁, w₂, ... , w_k}  dengan  merupakan himpunan k titik yang berada di G, kode metrik dari v terhadap himpunan w merupakan k-vektor yang didefinisikan

code_w(v)=(d(v,w₁), d(v,w₂), ..., d(v,w_k))

Dengan d(u,v)   merupakan lintasan terpendek yang menghubungkan titik u dan v. Himpunan W himpunan bagian dari V(G) disebut himpunan metrik lokal di G jika code_w(v) tidak sama dengan code_w(u) untuk setiap u yang adjacent di G. Himpunan metrik lokal dengan kardinalitas terkecil disebut basis metrik lokal. Kardinalitas basis metrik lokal disebut dimensi metrik lokal yang dinotasikan dengan dim_l(G). Sebagaimana yang diketahui, menghitung dimensi metrik lokal suatu graf termasuk NP-complete, yaitu suatu permasalahan matematika yang belum ada algoritma yang efektif untuk menyelesaikannya. Pada jurnal ini akan disajikan nilai dari dimensi metrik lokal dari graf hasil perkalian kuat, khususnya perkalian kuat pada graf bintang.