×

The multiresolving sets of graphs with prescribed multisimilar equivalence classes. (English) Zbl 1486.05156

Summary: For a set \(W = \{w_1, w_2, \dots, w_k\}\) of vertices and a vertex \(v\) of a connected graph \(G\), the multirepresentation of \(v\) with respect to \(W\) is the \(k\)-multiset \(m r(v \mid W) = \{d (v, w_1), d (v, w_2),\dots, d (v, w_k)\}\), where \(d(v, w_i)\) is the distance between the vertices \(v\) and \(w_i\) for \(i = 1,2, \dots, k\). The set \(W\) is a multiresolving set of \(G\) if every two distinct vertices of \(G\) have distinct multirepresentations with respect to \(W\). The minimum cardinality of a multiresolving set of \(G\) is the multidimension \(\operatorname{dim}_M(G)\) of \(G\). It is shown that, for every pair \(k, n\) of integers with \(k \geq 3\) and \(n \geq 3(k - 1)\), there is a connected graph \(G\) of order \(n\) with \(\operatorname{dim}_M(G) = k\). For a multiset \(\{a_1, a_2, \dots, a_k \}\) and an integer \(c\), we define \(\{a_1, a_2, \dots, a_k \} +\{c,c, \dots, c\} =\{a_1 + c, a_2 + c, \dots, a_k + c\}\). A multisimilar equivalence relation \(R_W\) on \(V(G)\) with respect to \(W\) is defined by \(u R_W v\) if \(m r(u \mid W) = m r (v\mid W) + \{c_W (u, v), c_W (u,v), \dots, c_W (u,v)\}\) for some integer \(c_W(u, v)\). We study the relationship between the elements in multirepresentations of vertices that belong to the same multisimilar equivalence class and also establish the upper bound for the cardinality of a multisimilar equivalence class. Moreover, a multiresolving set with prescribed multisimilar equivalence classes is presented.

MSC:

05C35 Extremal problems in graph theory
05C12 Distance in graphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chartrand, G.; Eroh, L.; Johnson, M. A.; Oellermann, O. R., Resolvability in graphs and the metric dimension of a graph, Discrete Applied Mathematics, 105, 1-3, 99-113 (2000) · Zbl 0958.05042
[2] Harary, F.; Melter, R. A., On the metric dimension of a graph, Ars Combinatoria, 2, 191-195 (1976) · Zbl 0349.05118
[3] Slater, P. J., Leaves of trees, Congressus Numerantium, 14, 549-559 (1975)
[4] Slater, P. J., Dominating and reference sets in a graph, Journal of Mathematical and Physical Sciences, 22, 4, 445-455 (1988) · Zbl 0656.05057
[5] Johnson, M., Browsable structure-activity datasets, Advances in Molecular Similarity Volume 2. Advances in Molecular Similarity Volume 2, Advances in Molecular Similarity, 2, 153-170 (1999), Elsevier
[6] Hulme, B. L.; Shiver, A. W.; Slater, P. J., FIRE, a subroutine for fire protection network analysis (SAND 81-1261) (1981), New Mexico: Sandia National Laboratories, New Mexico
[7] Hulme, B. L.; Shiver, A. W.; Slater, P. J., Computing minimum cost fire protection (SAND 820809 (1982), New Mexico: Sandia National Laboratories, New Mexico
[8] Hulme, B. L.; Shiver, A. W.; Slater, P. J., A Boolean Algebraic Analysis of Fire Protection, North-Holland Mathematics Studies, 95, C, 215-227 (1984) · Zbl 0551.90052
[9] Khuller, S.; Rsghavachari, B.; Rosenfeld, A., Localization in graphs (CS-TR-3326) (1994), Maryland: University of Maryland, Maryland
[10] Saenpholphat, V., On multiset dimension in graphs, Academic SWU, 1, 193-202 (2009)
[11] Simanjuntak, R.; Vetrík, T.; Mulia, P. B., The multiset dimension of graphs, Discrete Applied Mathematics
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.