On the local metric dimension of graphs

Resumen

-Justication and Needs for the Research Graphs may be used to model a large variety of network structures. For instance, in computer networks, servers, hosts or hubs can be represented as vertices in a graph and edges can represent connections between them. Likewise, the Web, social networks or transportation infrastructures can be modelled as graphs, where the vertices represent webpages, users and population centres, respectively; and the edges represent hyperlinks, personal relations, and roads, in that order. In the aforementioned graph-based representation of a computer network, each vertex may be seen as a possible location for an intruder (fault in the network, spoiled device, unauthorized connection) and, in this sense, a correct surveillance of each vertex of the graph to control such a possible intruder would be worthwhile. According to this fact, it would be desirable to uniquely recognize each vertex of the graph. In order to solve this problem, Slater [22] brought in the notion of locating sets and locating number of graphs. Also, Harary and Melter [10] independently introduced the same concept, but using the terms resolving sets and metric dimension to refer to locating sets and locating number, respectively. Moreover, in a more recent article, by SebŁo and Tannier [20], the terminology of metric generators and metric dimension for the concepts mentioned above, began to be used. These terms arose from the notion of metric generators of metric spaces, introduced by Blumenthal in [1]. In the thesis we follow this terminology. Informally, a metric generator is an ordered subset S of vertices in a graph G, such that every vertex of G is uniquely determined by its vector of distances to the vertices in S. The cardinality of a minimum metric generator for G is called the metric dimension of G. After the first papers on this topic were published, some authors developed diverse theoretical works on the subject including, for example, [3, 4, 5, 6, 11, 14, 16, 18, 21, 24]. Several applications of the metric generators have also been presented. In Chemistry, a usual representation for the structure of a chemical compound is a labeled graph where the vertex and edge labels specify the atom and bond types, respectively. As described in [6], metric generators allow to obtain unique representations for chemical substances. In particular, they were used in pharmaceutical research for discovering patterns common to a variety of drugs, as described in [12]. Furthermore, this topic has some applications to problems of pattern recognition and image processing, some of which involve the use of hierarchical data structures [15]. Some interesting connections between metric generators in graphs and the Mastermind game or coin weighing have been presented in [4]. Apart from the initial concept of metric generator, numerous variations of the concept have been studied, such as resolving dominating sets [2], independent resolving sets [8], connected resolving sets [19], adjacency generators [11], strong metric generators [20], local metric generators [17], locating-dominating sets [23], identifying codes [13], metric colorings [7] and k-metric generators [9]. In this thesis, we focus on the problem of computing the local metric dimension of graphs, which is the minimum cardinality among all local metric generators. - Methodology We used the most common methodology in mathematics research, which is based on deductive reasoning for theorem proving, in combination with trial-and-error experimentation for a part of the computational component of the study. We also enrolled in exchange of ideas, via collaboration with researchers from other institutions, the presentation of partial results in specialized conferences and their publication in ISI-JCR journals (three articles published and one additional article submitted). - Contribution: In this thesis, we focus on the problem of computing the local metric dimension of graphs. We first report on the state of the art on local metric dimension and present some original results in which we characterize all graphs achieving some bounds previously obtained in [23]. Secondly, we obtain closed formulas or tight bounds on the local metric dimension of several families of graphs, including strong product graphs, corona product graphs, rooted product graphs and lexicographic product graphs. Finally, we introduce the study of simultaneous local metric dimension and we give some general results on this new research line. For instance, we show that the problem of computing the simultaneous local metric dimension of a family of graphs on a common vertex set is NP-Hard. References: [1] R. Adar, L. Epstein, Models for the k-metric dimension, arXiv:1410.4209 [cs.DS]. [2] R. Adar, L. Epstein, The weighted 2-metric dimension of trees in the non-landmarks model, arXiv:1501.05197 [cs.DS]. [3] R. F. Bailey, P. J. Cameron, Base size, metric dimension and other invariants of groups and graphs, Bulletin of the London Mathematical Society 43 (2) (2011) 209-242. [4] G. Barragán-Ramírez, C. G. Gómez, J. A. Rodríguez-Velázquez, Closed formulae for the local metric dimension of corona product graphs, Electronic Notes in Discrete Mathematics 46 (0) (2014) 27-34, Jornadas de Matematica Discreta y Algorítmica. [5] Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Homann, M. Mihalak, L. Ram, Network discovery and verification, in: D. Kratsch (ed.), Graph-Theoretic Concepts in Computer Science, vol. 3787 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2005, pp. 127-138. [6] J. Díaz, O. Pottonen, M. Serna, E. van Leeuwen, On the complexity of metric dimension, in: L. Epstein, P. Ferragina (eds.), Algorithms-ESA 2012, vol. 7501 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2012, pp. 419-430. [7] H. Fernau, J. A. Rodríguez-Velazquez, On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results, arXiv:1309.2275 [math.CO]. [8] F. Foucaud, R. Klasing, P. J. Slater, Centroidal bases in graphs, Networks 64 (2) (2014) 96-108. [9] F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Combinatoria 2 (1976) 191-195. [10] C. Hernando, M. Mora, P. J. Slater, D. R. Wood, Fault-tolerant metric dimension of graphs, in: M. Changat, S. Klavzar, H. M. Mulder, A.Vijayakumar (eds.), Convexity in Discrete Structures, no. 5 in RMS Lecture Notes Series, ramanujan mathematical society ed., 2008, pp. 81-85. [11] M. Jannesari, B. Omoomi, The metric dimension of the lexicographic product of graphs, Discrete Mathematics 312 (22) (2012) 3349-3356. [12] M. Johnson, Browsable structure-activity datasets, in: R. Carbó-Dorca, P. Mezey (eds.), Advances in Molecular Similarity, chap. 8, JAI Press Inc, Stamford, Connecticut, 1998, pp. 153-170. [13] S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Applied Mathematics 70 (3) (1996) 217-229. [14] J. Kratica, M. Cangalovic, V. Kovacevic-Vujcic, Computing minimal doubly resolving sets of graphs, Computers & Operations Research 36 (7) (2009) 2149-2159. [15] J. Kratica, V. Kovacevic-Vujcic, M. Cangalovic, M. Stojanovic, Minimal doubly resolving sets and the strong metric dimension of some convex polytopes, Applied Mathematics and Computation 218 (19) (2012) 9790-9801. [16] D. Kuziak, I. G. Yero, J. A. Rodríguez-Velázquez, On the strong metric dimension of coronavproduct graphs and join graphs, Discrete Applied Mathematics 161 (7-8) (2013) 1022-1027. [17] P. Manuel, R. Bharati, I. Rajasingh, C. Monica M, On minimum metric dimension of honeycomb networks, Journal of Discrete Algorithms 6 (1) (2008) 20-27, selected papers from AWOCA 2005 Sixteenth Australasian Workshop on Combinatorial Algorithms. [18] R. A. Melter, I. Tomescu, Metric bases in digital geometry, Computer Vision, Graphics, and Image Processing 25 (1) (1984) 113-121. [19] F. Okamoto, B. Phinezy, P. Zhang, The local metric dimension of a graph, Mathematica Bohemica 135 (3) (2010) 239-255. [20] Y. Ramírez-Cruz, O. R. Oellermann, J. A. Rodríguez-Velázquez, The simultaneous metric dimension of graph families, Discrete Applied Mathematics 198 (2016) 241-250. [21] A. Sebo, E. Tannier, On metric generators of graphs, Mathematics of Operations Research 29 (2) (2004) 383-393. [22] P. J. Slater, Leaves of trees, Congressus Numerantium 14 (1975) 549-559. [23] R. Trujillo-Rasua, I. G. Yero, k-metric antidimension: A privacy measure for social graphs, Information Sciences 328 (2016) 403-417. [24] I. G. Yero, D. Kuziak, J. A. Rodríguez-Velázquez, On the metric dimension of corona product graphs, Computers & Mathematics with Applications 61 (9) (2011) 2793-2798.