THE LOCATING-CHROMATIC NUMBER OF TREES AND CHARACTERIZATION OF TREES HAVING LARGE LOCATING-CHROMATIC NUMBER

• Main Author: KASTIKA SYOFYAN (NIM: 30113009), DIAN
• Format: Dissertations
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/21725
• Institution: Institut Teknologi Bandung

The investigation on the locating chromatic number of graphs was firstly studied by <br /> <br /> <br /> Chartrand et.al on 2002 and now it has received much development. The concept of <br /> <br /> <br /> the locating chromatic number of graphs is a special case of the partition dimension <br /> <br /> <br /> of graphs. The locating-chromatic number of a graph G is defined as the cardinality <br /> <br /> <br /> of a minimum resolving partition of the vertex set V(G) such that all vertices have <br /> <br /> <br /> distinct coordinates with respect to this partition and every two adjacent vertices in <br /> <br /> <br /> G must not be contained in the same partition class. In this case, the coordinate of <br /> <br /> <br /> a vertex is expressed in terms of the distances of the vertex to all partition classes. <br /> <br /> <br /> The locating-chromatic numbers for some classes of graphs have been studied. <br /> <br /> <br /> However, the results are still very limited. One class of graphs which has received <br /> <br /> <br /> much attention in studying its locating-chromatic number is trees. However, up <br /> <br /> <br /> to now the results are still very limited and still far from satisfactory. As one of <br /> <br /> <br /> the important classes, trees have received much studies for various graph notions <br /> <br /> <br /> and concepts. The study of the locating-chromatic numbers for trees is still limited <br /> <br /> <br /> only to its subclasses such as paths, stars, double stars, amalgamation of stars, <br /> <br /> <br /> firecrackers, caterpillars, banana trees, n-ary trees, and lobsters. Therefore, in this <br /> <br /> <br /> dissertation, we examine the locating-chromatic number of some other classes of <br /> <br /> <br /> trees. <br /> <br /> <br /> The classes of trees studied in this dissertation are all trees having maximum degree <br /> <br /> <br /> 3 or 4, i.e. the trees that can be embedded in two-dimensional grid and binary <br /> <br /> <br /> trees. We show that the upper bound on the locating-chromatic number of trees <br /> <br /> <br /> embedded in two-dimensional grid is 5. Furthermore, we derive the upper bound <br /> <br /> <br /> on the locating chromatic number of binary trees depending on the diameter of <br /> <br /> <br /> such trees. This dissertation also discusses the locating-chromatic number of trees <br /> <br /> <br /> that are obtained by a graph operation. The graph operations investigated are the <br /> <br /> <br /> corona product and the edge-amalgamation on trees. The upper and lower bounds <br /> <br /> <br /> on the locating-chromatic number of trees obtained by these operations are derived. <br /> <br /> <br /> The decision problem for the locating chromatic number of any graph is an NPcomplete <br /> <br /> <br /> problem. This means that there is no efficient algorithm to determine <br /> <br /> <br /> the locating-chromatic number of any graph. Furuya and Matsumoto on 2015 <br /> <br /> <br /> have constructed a locating coloring algorithm to estimate an upper bound on the locating-chromatic number of trees. This upper bound depends on the number <br /> <br /> <br /> of leaves and the number of local end-branch in trees. In this dissertation, we <br /> <br /> <br /> propose a different algorithm to estimate the upper bound. The upper bound, <br /> <br /> <br /> which is generated from this algorithm, depends on diameter, maximum degree, <br /> <br /> <br /> and maximum number of end-path in trees. In this dissertation we also show the <br /> <br /> <br /> upper bound is better than the upper bound of Furuya dan Matsumoto. <br /> <br /> <br /> The characterisations of all graphs having a certain locating chromatic number <br /> <br /> <br /> have also been done. Chartrand et.al on 2002 characterized all graphs of order n <br /> <br /> <br /> with locating chromatic number n; namely they are complete multipartite graphs. <br /> <br /> <br /> Furthermore, Chartrand and Zhang on 2003 also characterized all graphs of order <br /> <br /> <br /> n with locating chromatic number n&#1048576;1. All graphs with locating chromatic number <br /> <br /> <br /> 3 are determined by Asmiati and Baskoro on 2012 and 2013. In this dissertation, we <br /> <br /> <br /> characterize all trees of order n with locating-chromatic number n&#1048576;t, for t < n=2.