Author, as appears in the article.: Fernau, Henning; Rodriguez-Velazquez, Juan A.;
Department: Enginyeria Informàtica i Matemàtiques
URV's Author/s: Rodríguez Velázquez, Juan Alberto
Keywords: Np-hardness Metric dimension Local metric dimension Adjacency dimension
Abstract: 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.
Thematic Areas: 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
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-09-07
Papper version: info:eu-repo/semantics/publishedVersion
Link to the original source: https://www.sciencedirect.com/science/article/pii/S0166218X17305401
Licence document URL: https://repositori.urv.cat/ca/proteccio-de-dades/
Papper original source: Discrete Applied Mathematics. 236 (C): 183-202
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
Article's DOI: 10.1016/j.dam.2017.11.019
Entity: Universitat Rovira i Virgili
Journal publication year: 2018
Publication Type: Journal Publications
Repositori URV