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

Computing the metric dimension of a graph from primary subgraphs

  • Dades identificatives

    Identificador: imarina:5130633
    Handle: https://hdl.handle.net/20.500.11797/imarina5130633
    Autors:
    Kuziak, DorotaRodriguez-Velazquez, Juan AYero, Ismael G
    Resum:
    Let G be a connected graph. Given an ordered set W = {w1, . . . , wk} V (G) and a vertex u V (G), the representation of u with respect to W is the ordered k-tuple (d(u, w1), d(u, w2), . . . , d(u, wk)), where d(u, wi) denotes the distance between u and wi. The set W is a metric generator for G if every two different vertices of G have distinct representations. A minimum cardinality metric generator is called a metric basis of G and its cardinality is called 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 for the metric dimension of graphs with cut vertices. The main results are applied to specific constructions including rooted product graphs, corona product graphs, block graphs and chains of graphs.

  • Altres:

    Autor segons l'article: Kuziak, Dorota; Rodriguez-Velazquez, Juan A; Yero, Ismael G
    Departament: Enginyeria Informàtica i Matemàtiques
    Autor/s de la URV: Rodríguez Velázquez, Juan Alberto
    Paraules clau: Rooted product graphs Primary subgraphs Metric dimension Metric basis Corona product graphs
    Resum: Let G be a connected graph. Given an ordered set W = {w1, . . . , wk} V (G) and a vertex u V (G), the representation of u with respect to W is the ordered k-tuple (d(u, w1), d(u, w2), . . . , d(u, wk)), where d(u, wi) denotes the distance between u and wi. The set W is a metric generator for G if every two different vertices of G have distinct representations. A minimum cardinality metric generator is called a metric basis of G and its cardinality is called 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 for the metric dimension of graphs with cut vertices. The main results are applied to specific constructions including rooted product graphs, corona product graphs, block graphs and chains of graphs.
    Àrees temàtiques: Mathematics Matemática / probabilidade e estatística Discrete mathematics and combinatorics Ciência da computação Applied 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
    URL Document de llicència: https://repositori.urv.cat/ca/proteccio-de-dades/
    Referència a l'article segons font original: Discussiones Mathematicae Graph Theory. 37 (1): 273-293
    Referència de l'ítem segons les normes APA: Kuziak, Dorota; Rodriguez-Velazquez, Juan A; Yero, Ismael G (2017). Computing the metric dimension of a graph from primary subgraphs. Discussiones Mathematicae Graph Theory, 37(1), 273-293. DOI: 10.7151/dmgt.1934
    Entitat: Universitat Rovira i Virgili
    Any de publicació de la revista: 2017
    Tipus de publicació: Journal Publications

  • Paraules clau:

    Applied Mathematics,Discrete Mathematics and Combinatorics,Mathematics
    Rooted product graphs
    Primary subgraphs
    Metric dimension
    Metric basis
    Corona product graphs
    Mathematics
    Matemática / probabilidade e estatística
    Discrete mathematics and combinatorics
    Ciência da computação
    Applied mathematics

  • Documents:

    DocumentPrincipal

  • Cerca a google

    Search to google scholar