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

On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results

  • Datos identificativos

    Identificador: imarina:5133136
    Autores:
    Fernau, HenningRodriguez-Velazquez, Juan A.
    Resumen:
    The metric dimension is quite a well-studied graph parameter. Recently, the adjacency metric dimension and the local metric dimension have been introduced. We combine these variants and introduce the local adjacency metric dimension. We show that the (local) metric dimension of the corona product of a graph of order and some non-trivial graph equals times the (local) adjacency metric dimension of . This strong relation also enables us to infer computational hardness results for computing the (local) metric dimension, based on according hardness results for (local) adjacency metric dimension that we also provide. We also study combinatorial properties of the strong product of graphs and emphasize the role of different types of twins play in determining in particular the adjacency metric dimension of a graph.
  • Otros:

    Autor según el artículo: Fernau, Henning; Rodriguez-Velazquez, Juan A.;
    Departamento: Enginyeria Informàtica i Matemàtiques
    Autor/es de la URV: Rodríguez Velázquez, Juan Alberto
    Palabras clave: Np-hardness Metric dimension Local metric dimension Adjacency dimension
    Resumen: The metric dimension is quite a well-studied graph parameter. Recently, the adjacency metric dimension and the local metric dimension have been introduced. We combine these variants and introduce the local adjacency metric dimension. We show that the (local) metric dimension of the corona product of a graph of order and some non-trivial graph equals times the (local) adjacency metric dimension of . This strong relation also enables us to infer computational hardness results for computing the (local) metric dimension, based on according hardness results for (local) adjacency metric dimension that we also provide. We also study combinatorial properties of the strong product of graphs and emphasize the role of different types of twins play in determining in particular the adjacency metric dimension of a graph.
    Áreas temáticas: Mathematics, applied Matemática / probabilidade e estatística Linguística e literatura Interdisciplinar Ensino Engenharias iv Engenharias iii Engenharias i Discrete mathematics and combinatorics Ciências biológicas i 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-09-07
    Versión del articulo depositado: info:eu-repo/semantics/publishedVersion
    Enlace a la fuente original: https://www.sciencedirect.com/science/article/pii/S0166218X17305401
    URL Documento de licencia: https://repositori.urv.cat/ca/proteccio-de-dades/
    Referencia al articulo segun fuente origial: Discrete Applied Mathematics. 236 (C): 183-202
    Referencia de l'ítem segons les normes APA: Fernau, Henning; Rodriguez-Velazquez, Juan A.; (2018). On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results. Discrete Applied Mathematics, 236(C), 183-202. DOI: 10.1016/j.dam.2017.11.019
    DOI del artículo: 10.1016/j.dam.2017.11.019
    Entidad: Universitat Rovira i Virgili
    Año de publicación de la revista: 2018
    Tipo de publicación: Journal Publications
  • Palabras clave:

    Applied Mathematics,Discrete Mathematics and Combinatorics,Mathematics, Applied
    Np-hardness
    Metric dimension
    Local metric dimension
    Adjacency dimension
    Mathematics, applied
    Matemática / probabilidade e estatística
    Linguística e literatura
    Interdisciplinar
    Ensino
    Engenharias iv
    Engenharias iii
    Engenharias i
    Discrete mathematics and combinatorics
    Ciências biológicas i
    Ciência da computação
    Applied mathematics
  • Documentos:

  • Cerca a google

    Search to google scholar