LOCAL METRIC DIMENSION OF CIRCULANT GRAPH - RICARD PITOY (NIM: 20116009), CAESAR
The concept of resolving set and metric dimension of a graph was introduced by Harary and Melter in 1976. Later Okamoto et al. introduced the concept of local resolving set and local metric dimension in 2010. Let G=(V,E) be a simple graph, the distance between two vertices u and v in G, denoted by d(u,v), defined as the length of the shortest path connecting both u and v. Let W={w_1,w_2,...,w_k } be a nonempty subset of V(G) and v an arbitrary vertex in G, then the metric representation of v with respect to W, denoted by r(v│W), is the k-vector (d(v,u_1 ),d(v,u_2 ),...,d(v,u_k )). If all two distinct vertices in G have different metric representations with respect to W, then W is called a resolving set of G. A resolving set with the smallest cardinality is called a basis of G. The cardinality of a basis of a graph G is called the metric dimension of G and denoted by dim(G). If all two adjacent vertices in G have different metric representation with respect to W, then W is called a local resolving set of G. A local resolving set with the smallest cardinality is called a local basis of G. The cardinality of a local basis of a graph G is called the local metric dimension of G and denoted by lmd(G). Circulant graph C_n (a_1,a_2,...,a_k ) is a graph with set of vertices {v_0,v_1,...,v_(n-1) } and every vertex v_i is adjacent to v_((i+a_j ) mod n), j=1,2,...,k. The set {a_1,a_2,...,a_k } is called the connecting set for the circulant graph. In this thesis, we study the value of the local metric dimension of circulant graph with connecting sets {1,2},{1,2,3} and {1,k}.