Articles producció científicaEnginyeria Informàtica i Matemàtiques

The Simultaneous Strong Metric Dimension of Graph Families

  • Identification data

    Identifier:  PC:1785
    Authors:  C. García-Gómez; A. Estrada-Moreno; Y. Ramírez-Cruz; J. A. Rodríguez-Velázquez
    Abstract:
    Let G be a family of graphs defined on a common (labelled) vertex set V. A set S¿ V is said to be a simultaneous strong metric generator for G if it is a strong metric generator for every graph of the family. The minimum cardinality among all simultaneous strong metric generators for G, denoted by Sd s(G) , is called the simultaneous strong metric dimension of G. We obtain general results on Sd s(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 NP-hard, even when restricted to families of trees.
  • Others:

    Link to the original source: https://link.springer.com/article/10.1007/s40840-015-0268-0
    Article's DOI: 10.1007/s40840-015-0268-0
    Journal publication year: 2016
    Entity: Universitat Rovira i Virgili
    Paper version: info:eu-repo/semantics/acceptedVersion
    Record's date: 2016-07-11
    First page: 175
    URV's Author/s: GARCÍA GÓMEZ, CARLOS; A. Estrada-Moreno; Y. Ramírez-Cruz; RODRÍGUEZ VELÁZQUEZ, JUAN ALBERTO
    Department: Enginyeria Informàtica i Matemàtiques
    Licence document URL: https://repositori.urv.cat/ca/proteccio-de-dades/
    Publication Type: Article
    Last page: 192
    ISSN: 0126-6705
    Author, as appears in the article.: C. García-Gómez; A. Estrada-Moreno; Y. Ramírez-Cruz; J. A. Rodríguez-Velázquez
    licence for use: https://creativecommons.org/licenses/by/3.0/es/
    Research group: Matemática Discreta
    Thematic Areas: Computer engineering
  • Keywords:

    Strong metric dimension
    Simultaneous metric dimension
  • Documents:

  • Cerca a google

    Search to google scholar