THE LOCATING CHROMATIC NUMBER FOR LOBSTER
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) suc...
Saved in:
| 主要作者: | |
|---|---|
| 格式: | Theses |
| 語言: | Indonesia |
| 主題: | |
| 在線閱讀: | https://digilib.itb.ac.id/gdl/view/33874 |
| 標簽: |
添加標簽
沒有標簽, 成為第一個標記此記錄!
|
| 機構: | Institut Teknologi Bandung |
| 語言: | Indonesia |
| 總結: | 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. |
|---|