Dimensi Metrik Lokal dari Graf Sederhana Hasil Perkalian Kuat

DEA ALVIONITA AZKA, Dr. Diah Junia Eksi Palupi,M.S; Dr. Al.Sutjijana,M.Sc

2019 | Tesis | MAGISTER MATEMATIKA

Diberikan graf terhubung dan sederhana G = (V(G),E(G)). Titik z elemen V(G) disebut pembeda dari titik x,y elemen V(G) jika jarak titik dari z ke x berbeda terhadap jarak titik z ke y. Himpunan W subset V(G) dengan W = {w_1,w_2,...,w_k} merupakan himpunan k titik yang berbeda di G, kode metrik dari v terhadap himpunan W merupakan k-vektor yang didefinisikan code_W(v) = (d(v,w_1), d(v,w_2),...,d(v,w_k)) dengan d(v,w_i) merupakan lintasan terpendek yang menghubungkan titik v dan w_i, untuk i = 1,2,...k. Himpunan W subset V(G) disebut himpunan metrik lokal di G jika code_W(v) tidak sama dengan code_W(u) untuk setiap u dan v yang bertetangga 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). Pada tesis ini akan disajikan batasan nilai dimensi metrik lokal pada graf hasil perkalian kuat, khususnya perkalian kuat pada graf path, graf lingkaran terhadap sebarang graf serta graf hasil perkalian kuat dari graf roda dan graf bintang.

Let G = (V(G),E(G)) be a connected simple graph . Vertex z is said to distinguish two vertices x,y in V(G) if the distance from z to x is different from the distance from z to y. A set W subseteq V(G) with W= {w_1,w_2,...,w_k} is set of k distinct vertices in G. The metric code of a vertex v of G with respect to W is k-vector by definition code_W(v) = (d(v,w_1), d(v,w_2),...,d(v,w_k)) where d(v,w_i) is the shortest distance from v to w_i, for i = 1,2,...k. The set W is a local metric set of G if code_W(u) not equal code_W(v) for every pair u,v of adjacent vertices of G. A local metric set with the minimum cardinality is called local metric basis and its cardinality is called the local metric dimension of G and denoted by dim_l(G). In this paper we study the problem of finding bound for the local metric dimension of strong product of graphs, especially strong product of path and cycle graph with other graphs, wheel graph and star graph.

Kata Kunci : Dimensi metrik, Dimensi Metrik Lokal, Perkalian Kuat