Geodesic
On the metric dimensions for sets of vertices
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 245-275 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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, {𝓁}-resolving sets were recently introduced. In this paper, we present new results regarding the {𝓁}-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 𝓁-solid-resolving sets, which is a natural generalisation of solid-resolving sets. We prove some general bounds and characterisations for 𝓁-solid-resolving sets and show how 𝓁-solid- and {𝓁}-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 𝓁-solid- and {𝓁}-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 
@article{DMGT_2023_43_1_a16,
     author = {Hakanen, Anni and Junnila, Ville and Laihonen, Tero and Puertas, Maria Luz},
     title = {On the metric dimensions for sets of vertices},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {245--275},
     year = {2023},
     volume = {43},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a16/}
}
TY  - JOUR
AU  - Hakanen, Anni
AU  - Junnila, Ville
AU  - Laihonen, Tero
AU  - Puertas, Maria Luz
TI  - On the metric dimensions for sets of vertices
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 245
EP  - 275
VL  - 43
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a16/
LA  - en
ID  - DMGT_2023_43_1_a16
ER  - 
%0 Journal Article
%A Hakanen, Anni
%A Junnila, Ville
%A Laihonen, Tero
%A Puertas, Maria Luz
%T On the metric dimensions for sets of vertices
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 245-275
%V 43
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a16/
%G en
%F DMGT_2023_43_1_a16
Hakanen, Anni; Junnila, Ville; Laihonen, Tero; Puertas, Maria Luz. On the metric dimensions for sets of vertices. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 1, pp. 245-275. http://geodesic.mathdoc.fr/item/DMGT_2023_43_1_a16/

[1] 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

[2] 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

[3] 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

[4] 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

[5] 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

[6] 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

[7] 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

[8] 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

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

[10] 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

[11] 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

[12] 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

[13] 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

[14] 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

[15] 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

[16] 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.