[go: up one dir, main page]
Skip to main content
SpringerLink
Log in

The Simultaneous Strong Metric Dimension of Graph Families

  • Published:
Bulletin of the Malaysian Mathematical Sciences Society Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. In fact, the boundary \(\partial (G)\) of a graph was defined first in [4] as the subgraph of G induced by the set mentioned in our article with the same notation.

References

  1. 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

  2. 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

  3. 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

    Article  MathSciNet  MATH  Google Scholar 

  4. 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#

  5. 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

    Article  MathSciNet  Google Scholar 

  6. 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

  7. 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

  8. 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

  9. 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

  10. Karp, R.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)

    Chapter  Google Scholar 

  11. 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

  12. 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

    MathSciNet  MATH  Google Scholar 

  13. 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

  14. 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

    Article  MathSciNet  MATH  Google Scholar 

  15. 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

  16. 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

  17. 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

    MathSciNet  MATH  Google Scholar 

  18. 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

    MathSciNet  MATH  Google Scholar 

  19. Kuziak, D.: Strong resolvability in product graphs, Doctoral Thesis, Universitat Rovira i Virgili (2014). http://deim.urv.cat/~juanalberto.rodriguez/Thesis-DorotaKuziak

  20. 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

  21. 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

  22. 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

  23. 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

  24. 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

  25. 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

  26. 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

  27. Sebö, A., Tannier, E.: On metric generators of graphs. Math. Oper. Res. 29(2), 383–393 (2004). doi:10.1287/moor.1030.0070

    Article  MathSciNet  MATH  Google Scholar 

  28. Slater, P.J.: Leaves of trees. Congressus Numerantium 14, 549–559 (1975)

    MathSciNet  MATH  Google Scholar 

  29. 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

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Av. Països Catalans 26, 43007, Tarragona, Spain

    A. Estrada-Moreno, C. García-Gómez, Y. Ramírez-Cruz & J. A. Rodríguez-Velázquez

Authors
  1. A. Estrada-Moreno
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. C. García-Gómez
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Y. Ramírez-Cruz
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. J. A. Rodríguez-Velázquez
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to J. A. Rodríguez-Velázquez.

Additional information

Communicated by Xueliang Li.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Estrada-Moreno, A., García-Gómez, C., Ramírez-Cruz, Y. et al. The Simultaneous Strong Metric Dimension of Graph Families. Bull. Malays. Math. Sci. Soc. 39 (Suppl 1), 175–192 (2016). https://doi.org/10.1007/s40840-015-0268-0

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s40840-015-0268-0

Keywords

Mathematics Subject Classification

Search

Navigation