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

On the Metric Dimensions for Sets of Vertices

Published Online: 24 Nov 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 10 Mar 2020
Accepted: 15 Sep 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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, {}-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

MSC 2010

[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. doi:10.1109/JSAC.2006.88401510.1109/JSAC.2006.884015Search in Google Scholar

[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. doi:10.1016/j.dam.2011.12.00910.1016/j.dam.2011.12.009Search in Google Scholar

[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. doi:/10.1137/05064186710.1137/050641867Search in Google Scholar

[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. doi:10.1016/S0166-218X(00)00198-010.1016/S0166-218X(00)00198-0Search in Google Scholar

[5] C.J. Colbourn and J.H. Dinitz, (Ed(s)), Handbook of Combinatorial Designs, Second Edition, in: Discrete Math. Appl. (Chapman & Hall/CRC, 2007). doi:10.1201/978142001054110.1201/9781420010541Search in Google Scholar

[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. doi:10.1016/j.disc.2015.12.02410.1016/j.disc.2015.12.024Search in Google Scholar

[7] A. Hakanen, V. Junnila and T. Laihonen, The solid-metric dimension, Theoret. Comput. Sci. 806 (2020) 156–170. doi:10.1016/j.tcs.2019.02.01310.1016/j.tcs.2019.02.013Search in Google Scholar

[8] A. Hakanen and T. Laihonen, On{}-metric dimensions in graphs, Fund. Inform. 162 (2018) 143–160. doi:10.3233/FI-2018-171810.3233/FI-2018-1718Search in Google Scholar

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

[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. doi:10.1016/S0252-9602(12)60204-510.1016/S0252-9602(12)60204-5Search in Google Scholar

[11] R. Isaacs, Infinite families of nontrivial trivalent graphs which are not tait colorable, Amer. Math. Monthly 82 (1975) 221–239. doi:10.1080/00029890.1975.1199380510.1080/00029890.1975.11993805Search in Google Scholar

[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. doi:10.1016/j.dam.2018.05.05110.1016/j.dam.2018.05.051Search in Google Scholar

[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. doi:10.1016/j.dam.2018.05.05210.1016/j.dam.2018.05.052Search in Google Scholar

[14] S. Khuller, B. Raghavachari and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (1996) 217–229. doi:10.1016/0166-218X(95)00106-210.1016/0166-218X(95)00106-2Search in Google Scholar

[15] T. Laihonen, The metric dimension for resolving several objects, Inform. Process. Lett. 116 (2016) 694–700. doi:10.1016/j.ipl.2016.06.00210.1016/j.ipl.2016.06.002Search in Google Scholar

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo