COMPUTATION OF METRIC DIMENSION OF TREE GRAPH, SYMMETRIC CUBIC GRAPH FROM FOSTER’S CENSUS, AND HYPERCUBE GRAPH

• Main Author: Farhanah Akadji, Afifah
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/70905
• Institution: Institut Teknologi Bandung

Let ????(????,????) be a simple and connected graph. The distance between two vertices ???? and ???? in ???? is the length of a shortest path between these two vertices and its denoted by ????(????,????). Let ????={????1,????2,?,????????} be a subset of ????(????). For every ?????????(????), the representation of a vertex ???? to ???? is ????(????|????)=(????(????,????1),????(????,????2),?,????(????,????????)). The set ???? is called a resolving set of ???? if all the vertices have a different representation. The resolving set with the smallest cardinality of ???? is called the basis of ????. The metric dimension of ???? is the cardinality of a basis of ???? and its denoted by ????????????(????). A tree graph is a connected graph and has no cycles. A symmetric cubic graph is an arc-transitive degree three regular graph. Foster (1932) conducted a census of all ????-order cubic symmetric graphs with ?????512. This census was continued by Conder et al. (2006) and they obtained a complete list of all symmetric cubic graphs with order ?????768. A hypercube graph ???????? is a graph with the set of all binary vectors of length n as its vertex set, and two neighboring vertices if the two vectors differ in exactly one position (coordinate). In this research, an algorithm is designed to determine the metric dimension and basis of tree graphs, symmetric cubic graphs, and hypercube graphs. The tree graph algorithm is based on the set of leaves and stem vertices. As a result, we obtained all metric dimensions and all possible basis for any tree ???????? with 4??????21. Meanwhile, the algorithm for symmetric cubic and hypercube graphs was developed as a greedy algorithm which constructs a resolving set starting from the set of one element by adding one new element until all the vertex representations are different. As a result, local optimal resolving sets are obtained for symmetric cubic graphs, and basis and metric dimensions for all hypercube graphs ???????? with 2??????11.