×

The simultaneous metric dimension of graph families. (English) Zbl 1327.05186

Summary: Let \(G = (V, E)\) be a connected graph. A vertex \(v \in V\) is said to resolve two vertices \(x\) and \(y\) if \(d_G(v, x) \neq d_G(v, y)\). A set \(S \subseteq V\) is said to be a metric generator for \(G\) if any pair of vertices of \(G\) is resolved by some element of \(S\). A minimum cardinality metric generator is called a metric basis, and its cardinality, \(\dim(G)\), the metric dimension of \(G\). A set \(S \subseteq V\) is said to be a simultaneous metric generator for a graph family \(\mathcal{G} = \{G_1, G_2, \ldots, G_k \}\), defined on a common (labeled) vertex set, if it is a metric generator for every graph of the family. A minimum cardinality simultaneous metric generator is called a simultaneous metric basis, and its cardinality the simultaneous metric dimension of \(\mathcal{G}\). We obtain sharp bounds for these invariants for general families of graphs and calculate closed formulae or tight bounds for the simultaneous metric dimension of several specific graph families. For a given graph \(G\) we describe a process for obtaining a lower bound on the maximum number of graphs in a family containing \(G\) that has simultaneous metric dimension equal to \(\dim(G)\). It is shown that the problem of finding the simultaneous metric dimension of families of trees is NP-hard. Sharp upper bounds for the simultaneous metric dimension of trees are established. The problem of finding this invariant for families of trees that can be obtained from an initial tree by a sequence of successive edge-exchanges is considered. For such families of trees sharp upper and lower bounds for the simultaneous metric dimension are established.

MSC:

05C40 Connectivity
05C05 Trees
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bailey, R. F.; Meagher, K., On the metric dimension of grassmann graphs, Discrete Math. Theor. Comput. Sci., 13, 4, 97-104 (2011) · Zbl 1286.05035
[2] Brigham, R. C.; Dutton, R. D., Factor domination in graphs, Discrete Math., 86, 1-3, 127-136 (1990) · Zbl 0722.05049
[3] Cáceres, J.; Hernando, C.; Mora, M.; Pelayo, I. M.; Puertas, M. L.; Seara, C.; Wood, D. R., On the metric dimension of cartesian product of graphs, SIAM J. Discrete Math., 21, 2, 423-441 (2007) · Zbl 1139.05314
[4] Chartrand, G.; Eroh, L.; Johnson, M. A.; Oellermann, O. R., Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math., 105, 1-3, 99-113 (2000) · Zbl 0958.05042
[5] Currie, J.; Oellermann, O. R., The metric dimension and metric independence of a graph, J. Combin. Math. Combin. Comput., 39, 157-167 (2001) · Zbl 0986.05040
[6] Feng, Z.; Li, W.; Xing, H.; Ma, Q., On the upper bounds of local inverse signed edge domination numbers in graphs, (Liu, C.; Wang, L.; Yang, A., Information Computing and Applications. Information Computing and Applications, Communications in Computer and Information Science, vol. 307 (2012), Springer: Springer Berlin Heidelberg), 368-372
[7] Guo, J.; Wang, K.; Li, F., Metric dimension of some distance-regular graphs, J. Comb. Optim., 26, 190-197 (2013) · Zbl 1298.90121
[8] Harary, F.; Melter, R. A., On the metric dimension of a graph, Ars Combin., 2, 191-195 (1976) · Zbl 0349.05118
[9] Haynes, T. W.; Henning, M. A.; Howard, J., Locating and total dominating sets in trees, Discrete Appl. Math., 154, 8, 1293-1300 (2006) · Zbl 1091.05051
[10] Hernando, C.; Mora, M.; Pelayo, I. M.; Seara, C.; Cáceres, J.; Puertas, M. L., On the metric dimension of some families of graphs, Electron. Notes Discrete Math., 22, 129-133 (2005), 7th International Colloquium on Graph Theory · Zbl 1182.05050
[11] Imran, M.; ul Haq Bokhary, S. A.; Ahmad, A.; Semaničová-Feňovčíková, A., On classes of regular graphs with constant metric dimension, Acta Math. Sin., 33, 1, 187-206 (2013) · Zbl 1289.05125
[12] Jannesari, M.; Omoomi, B., The metric dimension of the lexicographic product of graphs, Discrete Math., 312, 22, 3349-3356 (2012) · Zbl 1252.05187
[13] Johnson, M., Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Statist., 3, 2, 203-236 (1993), pMID: 8220404 · Zbl 0800.92106
[14] Johnson, M. A., Browsable structure-activity datasets, (Carbó-Dorca, R.; Mezey, P., Advances in Molecular Similarity, chap. 8 (1998), JAI Press Inc.: JAI Press Inc. Stamford, Connecticut), 153-170
[15] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York), 85-103 · Zbl 1467.68065
[16] Khuller, S.; Raghavachari, B.; Rosenfeld, A., Landmarks in graphs, Discrete Appl. Math., 70, 3, 217-229 (1996) · Zbl 0865.68090
[17] Melter, R. A.; Tomescu, I., Metric bases in digital geometry, Comput. Vis. Graph. Image Process., 25, 1, 113-121 (1984) · Zbl 0591.51023
[18] Oellermann, O. R.; Pawluck, C. D.; Stokke, A., The metric dimension of Cayley digraphs of abelian groups, Ars Combin., 81, 97-111 (2006) · Zbl 1189.05055
[19] Saenpholphat, V.; Zhang, P., Conditional resolvability in graphs: a survey, Int. J. Math. Math. Sci., 2004, 38, 1997-2017 (2004) · Zbl 1061.05028
[20] Saputro, S.; Simanjuntak, R.; Uttunggadewa, S.; Assiyatun, H.; Baskoro, E.; Salman, A.; Bača, M., The metric dimension of the lexicographic product of graphs, Discrete Math., 313, 9, 1045-1051 (2013) · Zbl 1263.05085
[21] Sebö, A.; Tannier, E., On metric generators of graphs, Math. Oper. Res., 29, 2, 383-393 (2004) · Zbl 1082.05032
[22] Slater, P. J., Leaves of trees, Congr. Numer., 14, 549-559 (1975)
[23] Yero, I. G.; Kuziak, D.; Rodríquez-Velázquez, J. A., On the metric dimension of corona product graphs, Comput. Math. Appl., 61, 9, 2793-2798 (2011) · Zbl 1221.05252
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.