Locating-chromatic number of the edge-amalgamation of trees

Dian Kastika Syofyan, Edy Tri Baskoro, Hilda Assiyatun


The investigation on the locating-chromatic number of a graph was initiated by Chartrand et al. (2002). This concept is in fact a special case of the partition dimension of a graph. This topic has received much attention. However, the results are still far from satisfaction. We can define the locating-chromatic number of a graph G as the smallest integer k such that there exists a k-partition of the vertex-set of G such that all vertices have distinct coordinates with respect to this partition. As we know that the metric dimension of a tree is completely solved. However, the locating-chromatic numbers for most of trees are still open. For i = 1, 2, . . . , t, let Ti be a tree with a fixed edge eoi called the terminal edge. The edge-amalgamation of all Tis denoted by Edge-Amal{Ti;eoi} is a tree formed by taking all the Tis and identifying their terminal edges. In this paper, we study the locating-chromatic number of the edge-amalgamation of arbitrary trees. We give lower and upper bounds for their locating-chromatic numbers and show that the bounds are tight.


edge-amalgamation; locating-chromatic number; terminal edge; tree

Full Text:


DOI: http://dx.doi.org/10.19184/ijc.2020.4.2.6


Asmiati, H. Assiyatun, and E.T. Baskoro, Locating-chromatic number of amalgamation of stars, ITB J. Sci. 43 A (1) (2011), 1–8.

Asmiati, E.T. Baskoro, H. Assiyatun, D. Suprijanto, R. Simanjuntak, and S. Uttunggadewa, The locating-chromatic number of firecracker graphs, Far East J. Math. Sci. 63:1 (2012), 11–23.

Asmiati, Bilangan kromatik lokasi graf pohon dan karakterisasi graf dengan bilangan kromatik lokasi 3, Disertasi Program Studi Doktor Matematika, Institut Teknologi Bandung, 2012 (in Indonesian).

E.T. Baskoro and Asmiati, Characterizing all trees with locating-chromatic number 3, Electron. J. Graph Theory Appl. 1 (2) (2013), 109–117.

G. Chartrand, D. Erwin, M.A. Henning, P.J. Slater, and P. Zhang, The locating-chromatic number of a graph, Bull. Inst. Combin. Appl. 36 (2002), 89–101.

D.K. Syofyan, E.T. Baskoro, and H. Assiyatun, On the locating-chromatic number of homogeneous lobster, AKCE Int. J. Graphs Comb. 10 (3) (2013), 245–252.

D.K. Syofyan, E.T. Baskoro, and H. Assiyatun, The locating-chromatic number of binary trees, Elsevier, The 2nd International Conference of Graph Theory and Information Security, 74 (2015), 79–83.

D.K. Syofyan, E.T. Baskoro, and H. Assiyatun, Trees with certain locating-chromatic number, J. Math. Fund. Sci. 48 (1) (2016), 39–47.

D. Welyyanti, E.T. Baskoro, R. Simanjuntak, and S. Uttunggadewa, On locating-chromatic number of complete n-ary tree, AKCE Int. J. Graphs Combin. 3 (2013), 309–315.


  • There are currently no refbacks.

ISSN: 2541-2205

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View IJC Stats