Articles producció científica> Enginyeria Informàtica i Matemàtiques

The metric dimension of strong product graphs

  • Dades identificatives

    Identificador: imarina:5128958
    Autors:
    Rodriguez-Velazquez, Juan AKuziak, DorotaYero, Ismael GSigarreta, Jose M
    Resum:
    For an ordered subset S = {s1; s2; ¿ sk} of vertices in a connected graph G, the metric representation of a vertex u with respect to the set S is the k-vector r(u|S) = (dG(v, s1); dG(v; s2); ¿; dG(v; sk)), where dG(x; y) represents the distance between the vertices x and y. The set S is a metric generator for G if every two different vertices of G have distinct metric representations with respect to S. A minimum metric generator is called a metric basis for G and its cardinality, dim(G), the metric dimension of G. It is well known that the problem of finding the metric dimension of a graph is NP-Hard. In this paper we obtain closed formulae and tight bounds for the metric dimension of strong product graphs. © 2015, North University of Baia Mare. All rights reserved.
  • Altres:

    Autor segons l'article: Rodriguez-Velazquez, Juan A; Kuziak, Dorota; Yero, Ismael G; Sigarreta, Jose M
    Departament: Enginyeria Informàtica i Matemàtiques
    Autor/s de la URV: Rodríguez Velázquez, Juan Alberto
    Paraules clau: Strong product graph Resolving set Metric generator Metric dimension Metric basis
    Resum: For an ordered subset S = {s1; s2; ¿ sk} of vertices in a connected graph G, the metric representation of a vertex u with respect to the set S is the k-vector r(u|S) = (dG(v, s1); dG(v; s2); ¿; dG(v; sk)), where dG(x; y) represents the distance between the vertices x and y. The set S is a metric generator for G if every two different vertices of G have distinct metric representations with respect to S. A minimum metric generator is called a metric basis for G and its cardinality, dim(G), the metric dimension of G. It is well known that the problem of finding the metric dimension of a graph is NP-Hard. In this paper we obtain closed formulae and tight bounds for the metric dimension of strong product graphs. © 2015, North University of Baia Mare. All rights reserved.
    Àrees temàtiques: Mathematics, applied Mathematics (miscellaneous) Mathematics (all) Mathematics General mathematics
    Accès a la llicència d'ús: https://creativecommons.org/licenses/by/3.0/es/
    Adreça de correu electrònic de l'autor: juanalberto.rodriguez@urv.cat
    Identificador de l'autor: 0000-0002-9082-7647
    Data d'alta del registre: 2024-10-26
    Versió de l'article dipositat: info:eu-repo/semantics/publishedVersion
    Enllaç font original: https://www.carpathian.cunbm.utcluj.ro/article/the-metric-dimension-of-strong-product-graphs/
    URL Document de llicència: https://repositori.urv.cat/ca/proteccio-de-dades/
    Referència a l'article segons font original: Carpathian Journal Of Mathematics. 31 (2): 261-268
    Referència de l'ítem segons les normes APA: Rodriguez-Velazquez, Juan A; Kuziak, Dorota; Yero, Ismael G; Sigarreta, Jose M (2015). The metric dimension of strong product graphs. Carpathian Journal Of Mathematics, 31(2), 261-268
    Entitat: Universitat Rovira i Virgili
    Any de publicació de la revista: 2015
    Tipus de publicació: Journal Publications
  • Paraules clau:

    Mathematics,Mathematics (Miscellaneous),Mathematics, Applied
    Strong product graph
    Resolving set
    Metric generator
    Metric dimension
    Metric basis
    Mathematics, applied
    Mathematics (miscellaneous)
    Mathematics (all)
    Mathematics
    General mathematics
  • Documents:

  • Cerca a google

    Search to google scholar