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

Computing the metric dimension of a graph from primary subgraphs

  • Datos identificativos

    Identificador: imarina:5130633
    Handle: https://hdl.handle.net/20.500.11797/imarina5130633
    Autores:
    Kuziak, DorotaRodriguez-Velazquez, Juan AYero, Ismael G
    Resumen:
    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.

  • Otros:

    Autor según el artículo: Kuziak, Dorota; Rodriguez-Velazquez, Juan A; Yero, Ismael G
    Departamento: Enginyeria Informàtica i Matemàtiques
    Autor/es de la URV: Rodríguez Velázquez, Juan Alberto
    Palabras clave: Rooted product graphs Primary subgraphs Metric dimension Metric basis Corona product graphs
    Resumen: 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.
    Áreas temáticas: Mathematics Matemática / probabilidade e estatística Discrete mathematics and combinatorics Ciência da computação Applied mathematics
    Acceso a la licencia de uso: https://creativecommons.org/licenses/by/3.0/es/
    Direcció de correo del autor: juanalberto.rodriguez@urv.cat
    Identificador del autor: 0000-0002-9082-7647
    Fecha de alta del registro: 2024-10-26
    Versión del articulo depositado: info:eu-repo/semantics/publishedVersion
    URL Documento de licencia: https://repositori.urv.cat/ca/proteccio-de-dades/
    Referencia al articulo segun fuente origial: Discussiones Mathematicae Graph Theory. 37 (1): 273-293
    Referencia 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
    Entidad: Universitat Rovira i Virgili
    Año de publicación de la revista: 2017
    Tipo de publicación: Journal Publications

  • Palabras clave:

    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

  • Documentos:

    DocumentPrincipal

  • Cerca a google

    Search to google scholar