METRIC DIMENSION AND LOCATING CHROMATIC NUMBER OF HALIN GRAPHS

• Main Author: APNI PURWASIH (30112013), IRA
• Format: Dissertations
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/22598
• Institution: Institut Teknologi Bandung

Let G(V;E) be a graph. The metric dimension of G is the cardinality of a minimum subset S of V (G) such that all vertices have different representations. In this case,the representation of a vertex v is a vector consisting of the distances from v to every vertex in S:The locating chromatic number of a graph G is defined as the cardinality of a minimum resolving partition of the vertex set V (G) such that all vertices have different coordinates, and every two adjacent vertices in G are not contained in the same partition class. In this case, the coordinate of a vertex in G is expressed in terms of the distances of this vertex to every partition class. The determination of metric dimension of an arbitrary graph is an NP-complete problem. Therefore, some heuristics approach have been developed to solve the problem. In addition, many studies in determining metric dimension and locating chromatic number of a graph have been done by considering to some graph classes, such as paths, cycles, trees and so forth. The study on characterizing all graphs that have certain metric dimension and locating chromatic number have been also carried out. However, the results are still very few and have not been satisfactory On this thesis, the metric dimension and the locating chromatic number of Halin graphs are studied. A Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross (this is called planar embedding), and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it. Finding the metric dimension on planar graphs is NP-complete, even on graphs of maximum degree six. A Halin graph has a lot of privileges. Every Halin graph is 3-connected and edgeminimal 3-connected. Every Halin graph is a Hamiltonian graph, and every edge of the graph belongs to a Hamiltonian cycle. Moreover, any Halin graph remains Hamiltonian after deletion of any vertex. More strongly, every Halin graph is almost pancyclic, even after contraction a single edge. Every Halin graph has treewidth 3.Therefore, many graph optimization problems that are NP-complete for arbitrary planar graphs, may be solved in linear time on Halin graphs. In this dissertation, we will show that the metric dimension of a Halin graph is bounded above by the sum of the metric dimensions of all subgraph that isomorphic to fans. Furthermore, the basis of the Halin graph can be constructed from the basis of the fan-subgraphs of order at least seven. In this dissertation, we determine the metric dimension of Halin graphs that formed of certain trees, such as a double star,an amalgamation of stars, and a caterpillar. Moreover, we derive a relation between the metric dimension of a Halin graph and the metric dimension of its subdivision. As a part of main results, we give the upper bound of the locating chromatic number of a Halin graph by constructing a locating coloring on Halin graph such that there is a single color on each its fan subgraph. In addition, the locating chromatic number of a Halin graph is bounded below by the locating chromatic number of its largest fan subgraph. In this dissertation, we derive the locating chromatic number of Halin graph formed from a certain tree, such as a double star graph and caterpillar. Then, we study the locating chromatic number of Halin graph with certain inner faces. Furthermore, we present the relationship between locating chromatic number of a graph with locating chromatic number of its subdivision.