THE LOCATING CHROMATIC NUMBER FOR LOBSTER

• Main Author: Kastika Syofyan, Dian
• Format: Theses
• Language: Indonesia
• Subjects: Matematika
• Online Access: https://digilib.itb.ac.id/gdl/view/33874
• Institution: Institut Teknologi Bandung

The concept of locating chromatic number of graph was introduced by Chartrand et al. [12] in 2002, as a special case of the concept of graph partition dimension. The locating chromatic number of a graph G can be dened as the cardinality of a minimum resolving partition of the vertex set V (G) such that all vertices have dierent coordinates, and every two neighboring 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 all partition classes. Determination of the locating chromatic number of an arbitrary graph is an NP-hard problem. Therefore, there is no an ecient algorithm to determine the locating-chromatic number of arbitrary graph. In addition, many studies in determining the locating chromatic number of a graph have been done by considering to some graph classes, such as paths, cycles, trees and graph which is obtained by operation of two graphs. In particular, for trees, the locating-chromatic number of some classes of trees are known, i.e. paths, double stars, caterpillars, recrackers, banana trees, amalgamation of star. On this thesis, we will determine the locating chromatic number of lobster as a type of trees with property that the removal of its endpoints results a caterpillar. We obtain the exact value of locating-chromatic number for homogeneous lobster and semihomogeneous lobster.