Edge metric dimensions via hierarchical product and integer linear programming
- PDF / 487,585 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 62 Downloads / 198 Views
Edge metric dimensions via hierarchical product and integer linear programming Sandi Klavžar1,2,3 · Mostafa Tavakoli4 Received: 9 March 2020 / Accepted: 8 November 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract If S = {v1 , . . . , vk } is an ordered subset of vertices of a connected graph G and e is an edge of G, then the vector r G (e|S) = (dG (v1 , e), . . . , dG (vk , e)) is the edge metric S-representation of e. If the vertices of G have pairwise different edge metric S-representations, then S is an edge metric generator for G. The cardinality of a smallest edge metric generator is the edge metric dimension edim(G) of G. A general sharp upper bound on the edge metric dimension of hierarchical products G(U ) H is proved. Exact formula is derived for the case when |U | = 1. An integer linear programming model for computing the edge metric dimension is proposed. Several examples are provided which demonstrate how these two methods can be applied to obtain the edge metric dimensions of some applicable graphs. Keywords Metric dimension · Edge metric dimension · Hierarchical product · Integer linear programming · Molecular graph
1 Introduction Graphs considered in this paper are connected, finite, and simple. If G is a graph and u, v ∈ V (G), then dG (u, v) denotes the shortest-path distance between u and v. If S = {v1 , . . . , vk } is an ordered subset of V (G), then the metric S-representation of a vertex u ∈ V (G) is the vector r G (u|S) = (dG (v1 , u), . . . , dG (vk , u)). The set S
B
Mostafa Tavakoli [email protected] Sandi Klavžar [email protected]
1
Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia
2
Faculty of Natural Sciences and Mathematics, University of Maribor, Maribor, Slovenia
3
Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
4
Department of Applied Mathematics, Faculty of Mathematical Sciences, Ferdowsi University of Mashhad, P.O. Box 1159, 91775 Mashhad, Iran
123
S. Klavžar, M. Tavakoli
distinguishes vertices u and v if r G (u|S) = r G (v|S) and S is a metric generator for G if each pair of vertices of G is distinguished by S. A metric generator of smallest cardinality is called a metric basis for G, its order being the metric dimension dim(G) of G. The sources for the metric dimension are papers [14,32]. Afterwards the concept was studied in depth, classical references include [5,7,8], papers dealing with applications of the metric dimension in modeling of real world problems include [17,21], while for some of the recent developments we refer to [36,41]. Several variations of the concept were also studied such as local resolving sets [28], strong resolving sets [27], strong resolving partitions [25,39], k-metric generators [9], k-antiresolving sets [34], and mixed metric generators [18]. Distinguishing edges instead of vertices seems an utmost natural variation, hence it comes as a surprise that the edge metric dimension was introduced only recently in [19] as follows. Let G be a graph.
Data Loading...
