Trees with Certain Locating-chromatic Number
DOI:
https://doi.org/10.5614/j.math.fund.sci.2016.48.1.4Keywords:
color code, leaves, locating-chromatic number, stem, treeAbstract
The locating-chromatic number of a graph G can be defined as the cardinality of a minimum resolving partition of the vertex set V(G) such that all vertices have distinct coordinates with respect to this partition and every two adjacent vertices in G are not contained in the same partition class. In this case, the coordinate of a vertex v in G is expressed in terms of the distances of v to all partition classes. This concept is a special case of the graph partition dimension notion. Previous authors have characterized all graphs of order n with locating-chromatic number either n or n-1. They also proved that there exists a tree of order n, n5, having locating-chromatic number k if and only if k?{3,4,",n-2,n}. In this paper, we characterize all trees of order n with locating-chromatic number n - t, for any integers n and t, where n> t+3 and 2 t < n/2.References
Chartrand, G., Erwin, D., Henning, M.A., Slater, P.J. & Zhang, P., The Locating-chromatics Number of A Graph, Bull. Inst. Combin. Appl., 36, pp. 89-101, 2002.
Asmiati, Assiyatun, H. & Baskoro, E.T., Locating-chromatic Number of Amalgamation of Stars, ITB J. Sci., 43A(1), pp. 1-8, 2011.
Asmiati, Baskoro, E.T., Assiyatun, H., Suprijanto, D., Simanjuntak, R. & Uttunggadewa, S., The Locating-Chromatic Number of Firecracker Graphs, Far East J. Math. Sci., 63(1), pp. 11-23, 2012.
Behtoei, A. & Omoomi, B., On the Locating Chromatic of Kneser Graphs, Discrete App. Math., 159, pp. 2214-2221, 2011.
Purwasih, I.A. & Baskoro, E.T., The Locating-chromatic Number of Certain Halin Graphs, AIP Conf Proc., 1450, pp. 342-345, 2012.
Behtoei, A. & Omoomi, B., On the Locating Chromatic of Cartesian Product of Graphs, Cornell University Library, http://arxiv.org/abs/ 1106.3453. (9 December 2012)
Behtoei, A., The Locating-chromatic Number of the Join of Graphs, Bull. Iran. Math. Soc., 40(6), pp. 1491-1504, 2014.
Syofyan, D.K., Baskoro, E.T. & Assiyatun, H., On the Locating-chromatic Number of Homogeneous Lobster, AKCE Int. J. Graphs Comb., 10(3), pp. 245-252, 2013.
Chartrand, G., Erwin, D., Henning, M.A., Slater, P.J. & Zhang, P., Graph of Order n with Locating-chromatic Number n-1, Discrete Math., 269(1-3), pp. 65-79, 2003.
Baskoro, E.T. & Asmiati, Characterizing All Trees with Locating-chromatic Number 3, Electronic Journal of Graph Theory and Applications, 1(2), pp. 109-117, 2013.
