Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The Simultaneous Metric Dimension of Families Composed by Lexicographic Product Graphs

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

Let \(\mathcal{G}\) be a graph family defined on a common (labeled) vertex set V. A set \(S\subseteq V\) is said to be a simultaneous metric generator for \(\mathcal{G}\) if for every \(G\in \mathcal{G}\) and every pair of different vertices \(u,v\in V\) there exists \(s\in S\) such that \(d_{G}(s,u)\ne d_{G}(s,v)\), where \(d_{G}\) denotes the geodesic distance. A simultaneous adjacency generator for \(\mathcal{G}\) is a simultaneous metric generator under the metric \(d_{G,2}(x,y)=\min \{d_{G}(x,y),2\}\). A minimum cardinality simultaneous metric (adjacency) generator for \(\mathcal{G}\) is a simultaneous metric (adjacency) basis, and its cardinality the simultaneous metric (adjacency) dimension of \(\mathcal{G}\). Based on the simultaneous adjacency dimension, we study the simultaneous metric dimension of families composed by lexicographic product graphs.

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

Similar content being viewed by others

Notes

  1. Adjacency generators were called adjacency resolving sets in [12].

  2. For any pair of vertices x, y belonging to different connected components of G we can assume that \(d_G(x,y)=\infty \) and so \(d_{G,t}(x,y)=t\) for any t greater than or equal to the maximum diameter of a connected component of G.

References

  1. Brigham, R.C., Chartrand, G., Dutton, R.D., Zhang, P.: Resolving domination in graphs. Math. Bohem. 128(1), 25–36 (2003). http://mb.math.cas.cz/mb128-1/3.html

  2. Brigham, R.C., Dutton, R.D.: Factor domination in graphs. Discret. Math. 86(1–3), 127–136 (1990). doi:10.1016/0012-365X(90)90355-L. http://www.sciencedirect.com/science/article/pii/0012365X9090355L

  3. Chartrand, G., Saenpholphat, V., Zhang, P.: The independent resolving number of a graph. Math. Bohem. 128(4), 379–393 (2003). http://mb.math.cas.cz/mb128-4/4.html

  4. Estrada-Moreno, A., Ramírez-Cruz, Y., Rodríguez-Velázquez, J.A.: On the adjacency dimension of graphs. Appl. Anal. Discret. Math. 10 (2016) (to appear). doi:10.2298/AADM151109022E

  5. Estrada-Moreno, A., Rodríguez-Velázquez, J.A., Yero, I.G.: The \(k\)-metric dimension of a graph. Appl. Math. Inf. Sci. 9(6), 2829–2840 (2015). http://naturalspublishing.com/files/published/05a21265hsd7y2

  6. Estrada-Moreno, A., Yero, I.G., Rodríguez-Velázquez, J.A.: The \(k\)-metric dimension of corona product graphs. Bull. Malays. Math. Sci. Soc. (2014) (to appear). http://math.usm.my/bulletin/pdf/acceptedpapers/2014-01-033-R1

  7. Fernau, H., Rodríguez-Velázquez, J.A.: On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results (2013). arXiv:1309.2275 [math.CO]. http://arxiv-web3.library.cornell.edu/abs/1309.2275

  8. Fernau, H., Rodríguez-Velázquez, J.A.: Notions of metric dimension of corona products: combinatorial and computational results. In: Computer Science-Theory and Applications. Lecture Notes in Computer Science, vol. 8476, pp. 153–166. Springer, Cham (2014)

  9. Hammack, R., Imrich, W., Klavžar, S.: Handbook of product graphs, 2 edn. In: Discrete Mathematics and its Applications. CRC Press (2011). http://www.crcpress.com/product/isbn/9781439813041

  10. Harary, F., Melter, R.A.: On the metric dimension of a graph. Ars Comb. 2, 191–195 (1976). http://www.ams.org/mathscinet-getitem?mr=0457289

  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. Sci. 33(1), 187–206 (2013). doi:10.1016/S0252-9602(12)60204-5. http://www.sciencedirect.com/science/article/pii/S0252960212602045

  12. Jannesari, M., Omoomi, B.: The metric dimension of the lexicographic product of graphs. Discret. Math. 312(22), 3349–3356 (2012). doi:10.1016/j.disc.2012.07.025. http://www.sciencedirect.com/science/article/pii/S0012365X12003317

  13. 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. http://www.tandfonline.com/doi/abs/10.1080/10543409308835060

  14. Johnson, M.: Browsable structure-activity datasets. In: Carbó-Dorca, R., Mezey, P. (eds.) Advances in Molecular Similarity, chap. 8, pp. 153–170. JAI Press Inc, Stamford (1998). http://books.google.es/books?id=1vvMsHXd2AsC

  15. Khuller, S., Raghavachari, B., Rosenfeld, A.: Landmarks in graphs. Discret. Appl. Math. 70(3), 217–229 (1996). doi:10.1016/0166-218X(95)00106-2. http://www.sciencedirect.com/science/article/pii/0166218X95001062

  16. Okamoto, F., Phinezy, B., Zhang, P.: The local metric dimension of a graph. Math. Bohem. 135(3), 239–255 (2010). http://dml.cz/dmlcz/140702

  17. Ramírez-Cruz, Y., Oellermann, O.R., Rodríguez-Velázquez, J.A.: Simultaneous resolvability in graph families. Electron. Notes Discret. Math. 46, 241–248 (2014). doi:10.1016/j.endm.2014.08.032. http://www.sciencedirect.com/science/article/pii/S157106531400033X

  18. 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. http://www.sciencedirect.com/science/article/pii/S0166218X1500298X

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

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

    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

    Y. Ramírez-Cruz, A. Estrada-Moreno & J. A. Rodríguez-Velázquez

Authors
  1. Y. Ramírez-Cruz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. Estrada-Moreno
    View author publications

    You can also search for this author in PubMed Google Scholar

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

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Y. Ramírez-Cruz.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ramírez-Cruz, Y., Estrada-Moreno, A. & Rodríguez-Velázquez, J.A. The Simultaneous Metric Dimension of Families Composed by Lexicographic Product Graphs. Graphs and Combinatorics 32, 2093–2120 (2016). https://doi.org/10.1007/s00373-016-1675-1

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-016-1675-1

Keywords

Mathematics Subject Classification

Search

Navigation