On {l}-Metric Dimensions in Graphs

• Autorzy: Hakanen A. , Laihonen T.

Identyfikatory

DOI

10.3233/FI-2018-1718

• Konferencja: RuFiDiM Conference, Russian-Finnish Symposium in Discrete Mathematics (5; 16-19.05. 2017; Turku; Finland)
• Języki publikacji: EN

Abstrakty

EN

A subset S of vertices is a resolving set in a graph if every vertex has a unique array of distances to the vertices of S. Consequently, we can locate any vertex of the graph with the aid of the distance arrays. The problem of finding the smallest cardinality of a resolving set in a graph has been widely studied over the years. In this paper, we consider sets S which can locate several, say up to l, vertices in a graph. These sets are called {l}-resolving sets and the smallest cardinality of such a set is the {l}-metric dimension of the graph. In this paper, we will give the {l}-metric dimensions for trees and king grids. We will show that there are certain vertices that necessarily belong to an {l}-resolving set. Moreover, we will classify all graphs whose {l}-metric dimension equals l.

Słowa kluczowe

EN

resolving set; metric dimension; metric basis; locating several vertices; forced vertices; king grid

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 162, nr 2/3
• Strony: 143--160
• Opis fizyczny: Bibliogr. 18 poz., rys.

Twórcy

autor

Hakanen A.

• Department of Mathematics and Statistics, University of Turku, FI-20014 Turku, Finland

autor

Laihonen T.

• Department of Mathematics and Statistics, University of Turku, FI-20014 Turku, Finland

Bibliografia

• [1] Slater PJ. Leaves of trees. In: Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975). Utilitas Math., Winnipeg, Man., 1975 pp. 549-559. Congressus Numerantium, No. XIV.
• [2] Harary F, Melter R. On the metric dimension of a graph. Ars Combinatoria, 1976. 2:191-195.
• [3] Lobstein A. Watching Systems, Identifying, Locating-Dominating and Discrminating Codes in Graphs, a bibliography. Published electronically at URL http://www.lri.fr/~lobstein/debutBIBidetlocdom.pdf.
• [4] Beerliova Z, Eberhard F, Erlebach T, Hall A, Hoffmann M, Mihalák M, Ram LS. Network Discovery and Verification. IEEE Journal on Selected Areas in Communications, 2006. 24(12):2168-2181. doi:10.1109/JSAC.2006.884015. URL https://doi.org/10.1109/JSAC.2006.884015.
• [5] Chartrand G, Eroh L, Johnson MA, Oellermann O. Resolvability in graphs and the metric dimension of a graph. Discrete Applied Mathematics, 2000. 105(1-3):99-113. doi:10.1016/S0166-218X(00)00198-0. URL https://doi.org/10.1016/S0166-218X(00)00198-0.
• [6] Khuller S, Raghavachari B, Rosenfeld A. Landmarks in Graphs. Discrete Applied Mathematics, 1996. 70(3):217-229. doi:10.1016/0166-218X(95)00106-2. URL https://doi.org/10.1016/0166-218X(95)00106-2.
• [7] Epstein L, Levin A, Woeginger GJ. The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases. Algorithmica, 2015. 72(4):1130-1171. doi:10.1007/s00453-014-9896-2. URL https://doi.org/10.1007/s00453-014-9896-2.
• [8] Cáceres J, Hernando MC, Mora M, Pelayo IM, Puertas ML, Seara C, Wood DR. On the Metric Dimension of Cartesian Products of Graphs. SIAM J. Discrete Math., 2007. 21(2):423-441. doi:10.1137/050641867. URL https://doi.org/10.1137/050641867.
• [9] Ramírez-Cruz Y, Oellermann OR, Rodríguez-Velázquez JA. The simultaneous metric dimension of graph families. Discrete Applied Mathematics, 2016. 198:241-250. doi:10.1016/j.dam.2015.06.012. URL https://doi.org/10.1016/j.dam.2015.06.012.
• [10] Kuziak D, Yero IG, Rodríguez-Velázquez JA. On the Strong Metric Dimension of Cartesian Sum Graphs. Fundam. Inform., 2015. 141(1):57-69. doi:10.3233/FI-2015-1263. URL https://doi.org/10.3233/FI-2015-1263.
• [11] Adar R, Epstein L. The k-metric dimension. J. Comb. Optim., 2017. 34(1):1-30. doi:10.1007/s10878-016-0073-1. URL https://doi.org/10.1007/s10878-016-0073-1.
• [12] Barragán-Ramírez GA, Rodríguez-Velázquez JA. The Local Metric Dimension of Strong Product Graphs. Graphs and Combinatorics, 2016. 32(4):1263-1278. doi:10.1007/s00373-015-1653-z. URL https://doi.org/10.1007/s00373-015-1653-z.
• [13] Cáceres J, Hernando MC, Mora M, Pelayo IM, Puertas ML. On the metric dimension of infinite graphs. Discrete Applied Mathematics, 2012. 160(18):2618-2626. doi:10.1016/j.dam.2011.12.009. URL https://doi.org/10.1016/j.dam.2011.12.009.
• [14] Fernau H, Heggernes P, van’t Hof P, Meister D, Saei R. Computing the metric dimension for chain graphs. Inf. Process. Lett., 2015. 115(9):671-676. doi:10.1016/j.ipl.2015.04.006. URL https://doi.org/10.1016/j.ipl.2015.04.006.
• [15] Rodríguez-Velázquez JA, Kuziak D, Yero IG, Sigarreta JM. The metric dimension of strong product graphs. Carpathian Journal of Mathematics, 2015. 31(2):261-268. URL http://www.jstor.org/stable/44000255.
• [16] Laihonen T. The metric dimension for resolving several objects. Inform. Process. Lett., 2016. 116(11):694-700. doi:10.1016/j.ipl.2016.06.002. URL http://dx.doi.org/10.1016/j.ipl.2016.06.002.
• [17] Hakanen A, Laihonen T. On resolving several objects in the king grid. In: Karhumäki J, Matiyasevich Y, Saarela A (eds.), Proceedings of the Fourth Russian Finnish Symposium in Discrete Mathematics. TUCS Lecture Notes No 26. ISBN 978-952-12-3547-4, 2017 pp. 60-64.
• [18] Hakanen A. Resolving sets and resolving several objects in the finite king grid. Master’s thesis, University of Turku, 2017. URL http://urn.fi/URN:NBN:fi-fe201709228699.