THE LOCATING-CHROMATIC NUMBER AND THE PARTITION DIMENSION OF FIBONACENE GRAPHS

• Main Author: Suryaningsih, Ratih
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/38768
• Institution: Institut Teknologi Bandung

Fibonacenes are unbranched catacondensed benzenoid hydrocarbons in which all the non-terminal hexagons are angularly annelated. A hexagon is said to be angularly annelated if the hexagon is adjacent to exactly two other hexagons and possesses two adjacent vertices of degree 2. Fibonacenes possess remarkable properties related with Fibonacci numbers. Various graph properties of fibonacenes have been extensively studied, such as their saturation numbers, independence numbers and Wiener index. The concept of partition of a connected graph was introduced by Chartrand et al [12] in 1998 which is an expansion of metric dimension concept. The partition dimension in a graph G, denoted by pd(G), is defined as the minimum cardinality of an ordered partition of a vertex set V (G) such as every vertex, with respect to the partition, has distict representation. The representation of a vertex is expressed in term of distances of this vertex to all partition classes. Next, the concept of locating-chromatic number of graph also was introduced by Chartrand et al [10] in 2002, as a combination of two concepts that is a coloring graph concept and partition dimention concept. The locating-chromatic number of a graph G, denoted by L(G), has a definition that is almost the same as the partition dimension except for the locating-chromatic number every two adjacent vertices in G are not contained in the same partition classes. Determination of the locating-chromatic number and the partition dimension of an arbitrary graph is an NP-hard problem. Therefore, there is no an efficient algorithm to determine the locating-chromatic number and the partition dimension of an arbitrary graph. The locating-chromatic number and the partition dimension can only be specified for certain graph classes. Some classes of graphs that have been known locating-chromatic number are at [10, 11, 3, 27, 28, 4, 18]. And some classes of graphs that have been known partition dimension are at [13, 33, 32, 1, 23, 22]. iii In this thesis, we will study about the partition dimension and the locating-chromatic number of any fibonacene graphs.