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

preprint2013arXivOpen access

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 nn and some non-trivial graph HH equals nn times the (local) adjacency metric dimension of HH. 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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.