LOCAL METRIC DIMENSION OF CIRCULANT GRAPH

• Main Author: RICARD PITOY (NIM: 20116009), CAESAR
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/26175
• Institution: Institut Teknologi Bandung

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. <br /> <br /> <br /> 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&#9474;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). <br /> <br /> <br /> 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. <br /> <br /> <br /> 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}. <br />