On the strong metric dimension of Cartesian and direct products of graphs

preprint2013arXivOpen access

Abstract

Let GG be a connected graph. A vertex ww {\em strongly resolves} a pair u,vu, v of vertices of GG if there exists some shortest u−wu-w path containing vv or some shortest v−wv-w path containing uu. A set WW of vertices is a {\em strong resolving set} for GG if every pair of vertices of GG is strongly resolved by some vertex of WW. The smallest cardinality of a strong resolving set for GG is called the {\em strong metric dimension} of GG. It is known that the problem of computing the strong metric dimension of a graph is NP-hard. In this paper we obtain closed formulae for the strong metric dimension of several families of Cartesian product graphs and direct product graphs.

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.