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

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 $n$ and some non-trivial graph $H$ equals $n$ times the (local) adjacency metric dimension of $H$. 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 different types of twins play in determining in particular the adjacency metric dimension of a graph.

29 pages

References in corpus (1)

• On the metric dimension of corona product graphs

Cited by in corpus (7)

• Computing the metric dimension of a graph from primary subgraphs
• The k-metric dimension of graphs: a general approach
• The $k$-metric dimension of the lexicographic product of graphs
• Simultaneous Resolvability in Families of Corona Product Graphs
• On the super domination number of lexicographic product graphs
• On the adjacency dimension of graphs
• The local metric dimension of strong product graphs