Article in volume
Authors:
Title:
On the metric dimensions for sets of vertices
PDFSource:
Discussiones Mathematicae Graph Theory 43(1) (2023) 245-275
Received: 2020-03-10 , Revised: 2020-09-15 , Accepted: 2020-09-15 , Available online: 2020-10-20 , https://doi.org/10.7151/dmgt.2367
Abstract:
Resolving sets were originally designed to locate vertices of a graph one at a
time. For the purpose of locating multiple vertices of the graph simultaneously,
$\{\ell\}$-resolving sets were recently introduced. In this paper, we present
new results regarding the $\{\ell\}$-resolving sets of a graph. In addition to
proving general results, we consider $\{2\}$-resolving sets in rook's graphs
and connect them to block designs. We also introduce the concept of
$\ell$-solid-resolving sets, which is a natural generalisation of
solid-resolving sets. We prove some general bounds and characterisations for
$\ell$-solid-resolving sets and show how $\ell$-solid- and $\{\ell\}$-resolving
sets are connected to each other. In the last part of the paper, we focus on
the infinite graph family of flower snarks. We consider the $\ell$-solid- and
$\{\ell\}$-metric dimensions of flower snarks. In two proofs regarding flower
snarks, we use a new computer-aided reduction-like approach.
Keywords:
resolving set, metric dimension, resolving several objects, block design, rook's graph, flower snark
References:
- Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffmann, M. Mihalák and L.S. Ram, Network discovery and verification, IEEE J. Sel. Areas Commun. 24 (2006) 2168–2181.
https://doi.org/10.1109/JSAC.2006.884015 - J. Cáceres, M.C. Hernando, M. Mora, I.M. Pelayo and M.L. Puertas, On the metric dimension of infinite graphs, Discrete Appl. Math. 160 (2012) 2618–2626.
https://doi.org/10.1016/j.dam.2011.12.009 - J. Cáceres, M.C. Hernando, M. Mora, I.M. Pelayo, M.L. Puertas, C. Seara and D.R. Wood, On the metric dimension of Cartesian products of graphs, SIAM J. Discrete Math. 21 (2007) 423–441.
https://doi.org//10.1137/050641867 - G. Chartrand, L. Eroh, M.A. Johnson, and O. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000) 99–113.
https://doi.org/10.1016/S0166-218X(00)00198-0 - C.J. Colbourn and J.H. Dinitz, (Ed(s)), Handbook of Combinatorial Designs, Second Edition, in: Discrete Math. Appl. (Chapman & Hall/CRC, 2007).
https://doi.org/10.1201/9781420010541 - A. Estrada-Moreno, I.G. Yero and J.A. Rodríguez-Velázquez, The k-metric dimension of the lexicographic product of graphs, Discrete Math. 339 (2016) 1924–1934.
https://doi.org/10.1016/j.disc.2015.12.024 - A. Hakanen, V. Junnila and T. Laihonen, The solid-metric dimension, Theoret. Comput. Sci. 806 (2020) 156–170.
https://doi.org/10.1016/j.tcs.2019.02.013 - A. Hakanen and T. Laihonen, On $\{\ell\}$-metric dimensions in graphs, Fund. Inform. 162 (2018) 143–160.
https://doi.org/10.3233/FI-2018-1718 - F. Harary and R. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195.
- M. Imran, S. Bokhary, A. Ahmad and A. Semaničová-Feňovčiková, On classes of regular graphs with constant metric dimension, Acta Math. Sci. Ser. B (Engl. Ed.) 33 (2013) 187–206.
https://doi.org/10.1016/S0252-9602(12)60204-5 - R. Isaacs, Infinite families of nontrivial trivalent graphs which are not tait colorable, Amer. Math. Monthly 82 (1975) 221–239.
https://doi.org/10.1080/00029890.1975.11993805 - C.X. Kang, I.G. Yero and E. Yi, The fractional strong metric dimension in three graph products, Discrete Appl. Math. 251 (2018) 190–203.
https://doi.org/10.1016/j.dam.2018.05.051 - A. Kelenc, N. Tratnik and I.G. Yero, Uniquely identifying the edges of a graph: The edge metric dimension, Discrete Appl. Math. 251 (2018) 204–220.
https://doi.org/10.1016/j.dam.2018.05.052 - S. Khuller, B. Raghavachari and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (1996) 217–229.
https://doi.org/10.1016/0166-218X(95)00106-2 - T. Laihonen, The metric dimension for resolving several objects, Inform. Process. Lett. 116 (2016) 694–700.
https://doi.org/10.1016/j.ipl.2016.06.002 - P.J. Slater, Leaves of trees, in: Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Congr. Numer. 14 (1975) 549–559.
Close