1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

The Neighbor-Locating-Chromatic Number of Trees and Unicyclic Graphs

Published Online: 24 Feb 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 24 May 2020
Accepted: 09 Jan 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

A k-coloring of a graph is neighbor-locating if any two vertices with the same color can be distinguished by the colors of their respective neighbors, that is, the sets of colors of their neighborhoods are different. The neighbor-locating chromatic number χNL(G) is the minimum k such that a neighbor-locating k-coloring of G exists. In this paper, we give upper and lower bounds on the neighbor-locating chromatic number in terms of the order and the degree of the vertices for unicyclic graphs and trees. We also obtain tight upper bounds on the order of trees and unicyclic graphs in terms of the neighbor-locating chromatic number. Further partial results for trees are also established.

Keywords

MSC 2010

[1] L. Alcon, M. Gutierrez, C. Hernando, M. Mora and I.M. Pelayo, Neighbor-locating colorings in graphs, Theoret. Comput. Sci. 806 (2020) 144–155. doi:10.1016/j.tcs.2019.01.03910.1016/j.tcs.2019.01.039Search in Google Scholar

[2] L. Alcon, M. Gutierrez, C. Hernando, M. Mora and I.M. Pelayo, The neighbor-locating-chromatic number of pseudotrees. arXiv:1903.11937v2 (2019)Search in Google Scholar

[3] E.T. Baskoro and A. Asmiati, Characterizing all trees with locating-chromatic number 3, Electron. J. Graph Theory Appl. 1 (2013) 109–117. doi:10.5614/ejgta.2013.1.2.410.5614/ejgta.2013.1.2.4Search in Google Scholar

[4] A. Behtoei and M. Anbarloei, The locating chromatic number of the join of graphs, Bull. Iranian Math. Soc. 40 (2014) 1491–1504.Search in Google Scholar

[5] A. Behtoei and M. Anbarloei, A bound for the locating chromatic numbers of trees, Trans. Comb. 4 (2015) 31–41.Search in Google Scholar

[6] A. Behtoei and B. Omoomi, On the locating chromatic number of Kneser graphs, Discrete Appl. Math. 159 (2011) 2214–2221. doi:10.1016/j.dam.2011.07.01510.1016/j.dam.2011.07.015Search in Google Scholar

[7] G.G. Chappell, J. Gimbel and C. Hartman, Bounds on the metric and partition dimensions of a graph, Ars Combin. 88 (2008) 349–366.Search in Google Scholar

[8] 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.Search in Google Scholar

[9] G. Chartrand, D. Erwin, M.A. Henning, P.J. Slater and P. Zhang, Graphs of ordernwith locating-chromatic numbern − 1, Discrete Math. 269 (2003) 65–79. doi:10.1016/S0012-365X(02)00829-410.1016/S0012-365X(02)00829-4Search in Google Scholar

[10] G. Chartrand, L. Lesniak and P. Zhang, Graphs and digraphs, Fifth Edition (Chapman and Hall/CRC Press, Taylor and Francis Group, 2011).10.1201/b14892Search in Google Scholar

[11] G. Chartrand, E. Salehi and P. Zhang, The partition dimension of a graph, Aequationes Math. 59 (2000) 45–54. doi:10.1007/PL0000012710.1007/PL00000127Search in Google Scholar

[12] M. Fehr, S. Gosselin and O.R. Oellermann, The partition dimension of Cayley di-graphs, Aequationes Math. 71 (2006) 1–18. doi:10.1007/s00010-005-2800-z10.1007/s00010-005-2800-zSearch in Google Scholar

[13] H. Fernau, J.A. Rodríguez-Velázquez and I. González-Yero, On the partition dimension of unicyclic graphs, Bull. Math. Soc. Sci. Math. Roumanie 57(105) (2014) 381–391.Search in Google Scholar

[14] C. Grigorious, S. Stephen, R. Rajan and M. Miller, On the partition dimension of circulant graphs, Comput. J. 60 (2017) 180–184. doi:10.1093/comjnl/bxw07910.1093/comjnl/bxw079Search in Google Scholar

[15] F. Harary and R. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195.Search in Google Scholar

[16] C. Hernando, M. Mora and I.M. Pelayo, Resolving dominating partitions in graphs, Discrete Appl. Math. 266 (2019) 237–251. doi:10.1016/j.dam.2018.12.00110.1016/j.dam.2018.12.001Search in Google Scholar

[17] J.A. Rodríguez-Velázquez, I. González Yero and M. Lemańska, On the partition dimension of trees, Discrete Appl. Math. 166 (2014) 204–209. doi:10.1016/j.dam.2013.09.02610.1016/j.dam.2013.09.026Search in Google Scholar

[18] P.J. Slater, Leaves of trees, in: Proc. 6th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Congr. Numer. 14 (1975) 549–559.Search in Google Scholar

[19] P.J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci. 22 (1988) 445–455.Search in Google Scholar

[20] D. Welyyanti, E.T. Baskoro, Darmaji, R. Simanjuntak and S. Uttunggadewa, On locating-chromatic number of complete n-ary tree, AKCE Int. J. Graphs Comb. 10 (2013) 309–315.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo