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

The equidistant dimension of graphs: NP-completeness and the case of lexicographic product graphs

  • Identification data

    Identifier: imarina:9368593
    Handle: https://hdl.handle.net/20.500.11797/imarina9368593
    Authors:
    Gispert-Fernandez, AdriaRodriuez-Velazquez, Juan Alberto
    Abstract:
    Let V ( G ) be the vertex set of a simple and connected graph G . A subset S subset of V ( G ) is a distance -equalizer set of G if, for every pair of vertices u , v E V ( G ) \ S , there exists a vertex in S that is equidistant to u and v . The minimum cardinality among the distance -equalizer sets of G is the equidistant dimension of G , denoted by xi ( G ). In this paper, we studied the problem of finding xi ( G o H ), where G o H denotes the lexicographic product of two graphs G and H . The aim was to express xi ( G o H ) in terms of parameters of G and H . In particular, we considered the cases in which G has a domination number equal to one, as well as the cases where G is a path or a cycle, among others. Furthermore, we showed that xi ( G )

  • Others:

    Author, as appears in the article.: Gispert-Fernandez, Adria; Rodriuez-Velazquez, Juan Alberto
    Department: Enginyeria Informàtica i Matemàtiques
    URV's Author/s: Rodríguez Velázquez, Juan Alberto
    Keywords: Distance-equalizer Distances in graph Distances in graphs Equidistant dimension Lexicographic product Np-complete problem
    Abstract: Let V ( G ) be the vertex set of a simple and connected graph G . A subset S subset of V ( G ) is a distance -equalizer set of G if, for every pair of vertices u , v E V ( G ) \ S , there exists a vertex in S that is equidistant to u and v . The minimum cardinality among the distance -equalizer sets of G is the equidistant dimension of G , denoted by xi ( G ). In this paper, we studied the problem of finding xi ( G o H ), where G o H denotes the lexicographic product of two graphs G and H . The aim was to express xi ( G o H ) in terms of parameters of G and H . In particular, we considered the cases in which G has a domination number equal to one, as well as the cases where G is a path or a cycle, among others. Furthermore, we showed that xi ( G )
    Thematic Areas: General mathematics Mathematics Mathematics (all) Mathematics (miscellaneous) Mathematics, applied
    licence for use: https://creativecommons.org/licenses/by/3.0/es/
    Author's mail: juanalberto.rodriguez@urv.cat
    Author identifier: 0000-0002-9082-7647
    Record's date: 2024-10-26
    Papper version: info:eu-repo/semantics/publishedVersion
    Link to the original source: https://www.aimspress.com/article/doi/10.3934/math.2024744
    Papper original source: Aims Mathematics. 9 (6): 15325-15345
    APA: Gispert-Fernandez, Adria; Rodriuez-Velazquez, Juan Alberto (2024). The equidistant dimension of graphs: NP-completeness and the case of lexicographic product graphs. Aims Mathematics, 9(6), 15325-15345. DOI: 10.3934/math.2024744
    Licence document URL: https://repositori.urv.cat/ca/proteccio-de-dades/
    Article's DOI: 10.3934/math.2024744
    Entity: Universitat Rovira i Virgili
    Journal publication year: 2024
    Publication Type: Journal Publications

  • Keywords:

    Mathematics,Mathematics (Miscellaneous),Mathematics, Applied
    Distance-equalizer
    Distances in graph
    Distances in graphs
    Equidistant dimension
    Lexicographic product
    Np-complete problem
    General mathematics
    Mathematics
    Mathematics (all)
    Mathematics (miscellaneous)
    Mathematics, applied

  • Documents:

    DocumentPrincipal

  • Cerca a google

    Search to google scholar