CHARACTERIZATION OF GRAPH WITH METRIC DIMENSION TWO

• Main Author: Galih Pratama, Dimas
• Format: Final Project
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/42431
• Institution: Institut Teknologi Bandung

Let ????=(????(????),????(????)) be a graph and ????={????1,????2,…,????????} be an ordered set, with ?????????(????),??????. For every ?????????(????), the metric representation of ???? with respect to ???? is defined by ????-vector ????(????|????)=(????(????,????1),????(????,????2),…,????(????,????????)). The set ???? is a resolving set of ???? if for all ????,?????????(????) with ????????? implies that ????(????|????)?????(????|????). The set ???? with minimum cardinality is called a basis, noted by ????(????). And the cardinality of ????(????) is called metric dimension of graph ????, noted by ????????????(????). Let ???? be a simple graph with vertex set ????(????) and ???? be a vertex in ????. Then, {????0,????1,…,????????} is called a distance partition of ????(????) with reference to the vertex ???? if ????0={????} and ???????? contains vertices which are at distance ???? from ????, for 0<?????????, where ???? is the eccentricity of ???? in graph ????. In this final project, we construct an exhaust4e algorithm and implement the algorithm in MATLAB to search for all undirected, unweighted graphs on ???? vertices with 3??????8, that have metric dimension two.