The Simultaneous Strong Metric Dimension of Graph Families
Tóm tắt
Let
$$\mathcal{G}$$
be a family of graphs defined on a common (labelled) vertex set V. A set
$$S\subset V$$
is said to be a simultaneous strong metric generator for
$$\mathcal{G}$$
if it is a strong metric generator for every graph of the family. The minimum cardinality among all simultaneous strong metric generators for
$$\mathcal{G}$$
, denoted by
$${\text {Sd}}_s(\mathcal{G})$$
, is called the simultaneous strong metric dimension of
$$\mathcal{G}$$
. We obtain general results on
$${\text {Sd}}_s(\mathcal{G})$$
for arbitrary families of graphs, with special emphasis on the case of families composed by a graph and its complement. In particular, it is shown that the problem of finding the simultaneous strong metric dimension of families of graphs is
$${\textit{NP}}$$
-hard, even when restricted to families of trees.
Tài liệu tham khảo
Brešar, B., Klavžar, S., Horvat, A.T.: On the geodetic number and related metric sets in cartesian product graphs. Discret. Appl. Math. 308(23), 5555–5561 (2008). http://www.sciencedirect.com/science/article/pii/S0012365X07008266
Cáceres, J., Puertas, M.L., Hernando, C., Mora, M., Pelayo, I.M., Seara, C.: Searching for geodetic boundary vertex sets. Electron. Note. Discret. Math. 19, 25–31 (2005). http://www.researchgate.net/publication/220082130_Searching_for_geodetic_boundary_vertex_sets/file/9fcfd50c50061192cb
Chartrand, G., Eroh, L., Johnson, M.A., Oellermann, O.R.: Resolvability in graphs and the metric dimension of a graph. Discret. Appl. Math. 105(1–3), 99–113 (2000). doi:10.1016/S0166-218X(00)00198-0
Chartrand, G., Erwin, D., Johns, G.L., Zhang, P.: Boundary vertices in graphs. Discret. Math. 263(1–3), 25–34 (2003). http://www.sciencedirect.com/science/article/pii/S0012365X02005678#
Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596–615 (1987). doi:10.1145/28869.28874
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York (1979). http://dl.acm.org/citation.cfm?id=578533
Harary, F., Melter, R.A.: On the metric dimension of a graph. Ars Combin. 2, 191–195 (1976). http://www.ams.org/mathscinet-getitem?mr=0457289
Johnson, M.: Structure-activity maps for visualizing the graph variables arising in drug design. J. Biopharm. Stat. 3(2), 203–236 (1993). doi:10.1080/10543409308835060
Johnson, M.: Browsable structure-activity datasets, In: R. Carbó-Dorca, P. Mezey (eds.), Advances in Molecular Similarity, chap. 8, pp. 153–170. JAI Press Inc, Stamford, Connecticut (1998). http://books.google.es/books?id=1vvMsHXd2AsC
Karp, R.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)
Khuller, S., Raghavachari, B., Rosenfeld, A.: Landmarks in graphs. Discret. Appl. Math. 70(3), 217–229 (1996). http://www.sciencedirect.com/science/article/pii/0166218X95001062
Kratica, J., Kovačević-Vujčić, V., Čangalović, M., Stojanović, M.: Minimal doubly resolving sets and the strong metric dimension of some convex polytopes. Appl. Math. Comput. 218(19), 9790–9801 (2012). doi:10.1016/j.amc.2012.03.047
Kratica, J., Kovačević-Vujčić, V., Čangalović, M.: Computing strong metric dimension of some special classes of graphs by genetic algorithms. Yugoslav J. Oper. Res. 18(2), 143–151 (2008). http://www.doiserbia.nb.rs/Article.aspx?id=0354-02430802143K
Kratica, J., Kovačević-Vujčić, V., Čangalović, M., Mladenović, N.: Strong metric dimension: a survey. Yugoslav J. Oper. Res. 24(2), 187–198 (2014). doi:10.2298/YJOR130520042K
Kratica, J., Kovačević-Vujčić, V., Čangalović, M., Stojanović, M.: Minimal doubly resolving sets and the strong metric dimension of Hamming graphs, Appl. Anal. Discret. Math. 6(1), 63–71 (2012). http://www.doiserbia.nb.rs/Article.aspx?ID=1452-86301100023K
Kuziak, D., Yero, I.G., Rodríguez-Velázquez, J.A.: On the strong metric dimension of corona product graphs and join graphs. Discret. Appl. Math. 161(7–8), 1022–1027 (2013). http://www.sciencedirect.com/science/article/pii/S0166218X12003897
Kuziak, D., Yero, I.G., Rodríguez-Velázquez, J.A.: Erratum to “On the strong metric dimension of the strong products of graphs”. Open Math. 13, 209–210 (2015). doi:10.1515/math-2015-0020
Kuziak, D., Yero, I.G., Rodríguez-Velázquez, J.A.: On the strong metric dimension of the strong products of graphs. Open Math. 13, 64–74 (2015). doi:10.1515/math-2015-0007
Kuziak, D.: Strong resolvability in product graphs, Doctoral Thesis, Universitat Rovira i Virgili (2014). http://deim.urv.cat/~juanalberto.rodriguez/Thesis-DorotaKuziak
May, T.R., Oellermann, O.R.: The strong dimension of distance-hereditary graphs. J. Comb. Math. Comb. Comput. 76, 59–73 (2011). http://www.combinatorialmath.ca/jcmcc/jcmcc76.html
Mladenović, N., Kratica, J., Kovačević-Vujčić, V., Čangalović, M.: Variable neighborhood search for the strong metric dimension problem, In: EURO Mini Conference. Electronic Notes in Discrete Mathematics, vol. 39, pp. 51–57. Elsevier Sci. B. V., Amsterdam (2012). doi:10.1016/j.endm.2012.10.008
Oellermann, O.R., Peters-Fransen, J.: The strong metric dimension of graphs and digraphs. Discret. Appl. Math. 155(3), 356–364 (2007). http://www.sciencedirect.com/science/article/pii/S0166218X06003015
Ramírez-Cruz, Y., Oellermann, O.R., Rodríguez-Velázquez, J.A.: The simultaneous metric dimension of graph families. Discret. Appl. Math. (2015). doi:10.1016/j.dam.2015.06.012
Ramírez-Cruz, Y., Oellermann, O.R., Rodríguez-Velázquez, J.A.: Simultaneous resolvability in graph families. Electron. Not. Discret. Math. 46(0), 241–248 (2014). http://www.sciencedirect.com/science/article/pii/S157106531400033X
Rodríguez-Velázquez, J.A., Yero, I.G., Kuziak, D., Oellermann, O.R.: On the strong metric dimension of cartesian and direct products of graphs. Discret. Math. 335(0), 8–19 (2014). http://www.sciencedirect.com/science/article/pii/S0012365X14002507
Savage, C.: Depth-first search and the vertex cover problem. Inf. Process. Lett. 14(5), 233–235 (1982). http://www.sciencedirect.com/science/article/pii/0020019082900229
Sebö, A., Tannier, E.: On metric generators of graphs. Math. Oper. Res. 29(2), 383–393 (2004). doi:10.1287/moor.1030.0070
Slater, P.J.: Leaves of trees. Congressus Numerantium 14, 549–559 (1975)
Yi, E.: On strong metric dimension of graphs and their complements. Acta Math. Sin. (Engl. Ser.) 29(8), 1479–1492 (2013). doi:10.1007/s10114-013-2365-z