DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

L. Alcón

Liliana Alcón

CMaLP, Universidad Nacional de La Plata

La Plata, Argentina

and CONICET, Argentina

email: liliana@mate.unlp.edu.ar

M. Gutierrez

Marisa Gutierrez

email: marisa@mate.unlp.edu.ar

C. Hernando

Carmen Hernando

email: carmen.hernando@upc.edu

M. Mora

Mercé Mora

Universitat Politècnica de Catalunya

email: merce.mora@upc.edu

I.M. Pelayo

Ignacio M. Pelayo

Universitat Politècnica de Catalunya

email: ignacio.m.pelayo@upc.edu

Title:

The neighbor-locating-chromatic number of trees and unicyclic graphs

PDF

Source:

Discussiones Mathematicae Graph Theory 43(3) (2023) 659-675

Received: 2020-05-24 , Revised: 2021-01-09 , Accepted: 2021-01-09 , Available online: 2021-02-06 , https://doi.org/10.7151/dmgt.2392

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 $\chi_{_{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:

coloring, location, neighbor-locating coloring, unicyclic graph, tree

References:

  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.
    https://doi.org/10.1016/j.tcs.2019.01.039
  2. L. Alcon, M. Gutierrez, C. Hernando, M. Mora and I.M. Pelayo, The neighbor-locating-chromatic number of pseudotrees (2019).
    arXiv: 1903.11937v2
  3. E.T. Baskoro and A. Asmiati, Characterizing all trees with locating-chromatic number $ 3$, Electron. J. Graph Theory Appl. 1 (2013) 109–117.
    https://doi.org/10.5614/ejgta.2013.1.2.4
  4. A. Behtoei and M. Anbarloei, The locating chromatic number of the join of graphs, Bull. Iranian Math. Soc. 40 (2014) 1491–1504.
  5. A. Behtoei and M. Anbarloei, A bound for the locating chromatic numbers of trees, Trans. Comb. 4 (2015) 31–41.
  6. A. Behtoei and B. Omoomi, On the locating chromatic number of Kneser graphs, Discrete Appl. Math. 159 (2011) 2214–2221.
    https://doi.org/10.1016/j.dam.2011.07.015
  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.
  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.
  9. G. Chartrand, D. Erwin, M.A. Henning, P.J. Slater and P. Zhang, Graphs of order $n$ with locating-chromatic number $n-1$, Discrete Math. 269 (2003) 65–79.
    https://doi.org/10.1016/S0012-365X(02)00829-4
  10. G. Chartrand, L. Lesniak and P. Zhang, Graphs and digraphs, Fifth Edition (Chapman and Hall/CRC Press, Taylor and Francis Group, 2011).
  11. G. Chartrand, E. Salehi and P. Zhang, The partition dimension of a graph, Aequationes Math. 59 (2000) 45–54.
    https://doi.org/10.1007/PL00000127
  12. M. Fehr, S. Gosselin and O.R. Oellermann, The partition dimension of Cayley digraphs, Aequationes Math. 71 (2006) 1–18.
    https://doi.org/10.1007/s00010-005-2800-z
  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.
  14. C. Grigorious, S. Stephen, R. Rajan and M. Miller, On the partition dimension of circulant graphs, Comput. J. 60 (2017) 180–184.
    https://doi.org/10.1093/comjnl/bxw079
  15. F. Harary and R. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195.
  16. C. Hernando, M. Mora and I.M. Pelayo, Resolving dominating partitions in graphs, Discrete Appl. Math. 266 (2019) 237–251.
    https://doi.org/10.1016/j.dam.2018.12.001
  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.
    https://doi.org/10.1016/j.dam.2013.09.026
  18. P.J. Slater, Leaves of trees, in: Proc. 6th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Congr. Numer. 14 (1975) 549–559.
  19. P.J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci. 22 (1988) 445–455.
  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.

Close