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

The simultaneous local metric dimension of graph families

  • Identification data

    Identifier: imarina:5131868
    Authors:
    Barragan-Ramirez, Gabriel AEstrada-Moreno, AlejandroRamirez-Cruz, YuniorRodriguez-Velazquez, Juan A
    Abstract:
    In a graph G = (V, E), a vertex v ¿ V is said to distinguish two vertices x and y if dG(v, x) ¿ dG(v, y). A set S ¿ V is said to be a local metric generator for G if any pair of adjacent vertices of G is distinguished by some element of S. A minimum local metric generator is called a local metric basis and its cardinality the local metric dimension of G. A set S ¿ V is said to be a simultaneous local metric generator for a graph family G = (G1, G2, . . . , Gk), defined on a common vertex set, if it is a local metric generator for every graph of the family. A minimum simultaneous local metric generator is called a simultaneous local metric basis and its cardinality the simultaneous local metric dimension of G. We study the properties of simultaneous local metric generators and bases, obtain closed formulae or tight bounds for the simultaneous local metric dimension of several graph families and analyze the complexity of computing this parameter.
  • Others:

    Author, as appears in the article.: Barragan-Ramirez, Gabriel A; Estrada-Moreno, Alejandro; Ramirez-Cruz, Yunior; Rodriguez-Velazquez, Juan A
    Department: Enginyeria Informàtica i Matemàtiques
    e-ISSN: 2073-8994
    URV's Author/s: Estrada Moreno, Alejandro / Rodríguez Velázquez, Juan Alberto
    Keywords: Simultaneity Local metric dimension Lexicographic product Corona product Complexity
    Abstract: In a graph G = (V, E), a vertex v ¿ V is said to distinguish two vertices x and y if dG(v, x) ¿ dG(v, y). A set S ¿ V is said to be a local metric generator for G if any pair of adjacent vertices of G is distinguished by some element of S. A minimum local metric generator is called a local metric basis and its cardinality the local metric dimension of G. A set S ¿ V is said to be a simultaneous local metric generator for a graph family G = (G1, G2, . . . , Gk), defined on a common vertex set, if it is a local metric generator for every graph of the family. A minimum simultaneous local metric generator is called a simultaneous local metric basis and its cardinality the simultaneous local metric dimension of G. We study the properties of simultaneous local metric generators and bases, obtain closed formulae or tight bounds for the simultaneous local metric dimension of several graph families and analyze the complexity of computing this parameter.
    Thematic Areas: Visual arts and performing arts Physics and astronomy (miscellaneous) Multidisciplinary sciences Modeling and simulation Mathematics, interdisciplinary applications Mathematics (miscellaneous) Mathematics (all) Matemática / probabilidade e estatística General mathematics Engineering (miscellaneous) Computer science (miscellaneous) Ciência da computação Chemistry (miscellaneous) Arts and humanities (miscellaneous) Architecture Applied mathematics
    licence for use: https://creativecommons.org/licenses/by/3.0/es/
    ISSN: 20738994
    Author's mail: alejandro.estrada@urv.cat juanalberto.rodriguez@urv.cat
    Author identifier: 0000-0001-9767-2177 0000-0002-9082-7647
    Record's date: 2024-10-26
    Journal volume: 9
    Papper version: info:eu-repo/semantics/publishedVersion
    Link to the original source: https://www.mdpi.com/2073-8994/9/8/132
    Licence document URL: https://repositori.urv.cat/ca/proteccio-de-dades/
    Papper original source: Symmetry-Basel. 9 (8): 132-
    APA: Barragan-Ramirez, Gabriel A; Estrada-Moreno, Alejandro; Ramirez-Cruz, Yunior; Rodriguez-Velazquez, Juan A (2017). The simultaneous local metric dimension of graph families. Symmetry-Basel, 9(8), 132-. DOI: 10.3390/sym9080132
    Article's DOI: 10.3390/sym9080132
    Entity: Universitat Rovira i Virgili
    Journal publication year: 2017
    Publication Type: Journal Publications
  • Keywords:

    Applied Mathematics,Architecture,Arts and Humanities (Miscellaneous),Chemistry (Miscellaneous),Computer Science (Miscellaneous),Engineering (Miscellaneous),Mathematics (Miscellaneous),Mathematics, Interdisciplinary Applications,Modeling and Simulation,Multidisciplinary Sciences,Physics and Astronomy (Miscellaneous),Visual Arts and Performi
    Simultaneity
    Local metric dimension
    Lexicographic product
    Corona product
    Complexity
    Visual arts and performing arts
    Physics and astronomy (miscellaneous)
    Multidisciplinary sciences
    Modeling and simulation
    Mathematics, interdisciplinary applications
    Mathematics (miscellaneous)
    Mathematics (all)
    Matemática / probabilidade e estatística
    General mathematics
    Engineering (miscellaneous)
    Computer science (miscellaneous)
    Ciência da computação
    Chemistry (miscellaneous)
    Arts and humanities (miscellaneous)
    Architecture
    Applied mathematics
  • Documents:

  • Cerca a google

    Search to google scholar