Computing the metric dimension of the categorial product of some graphs

ABSTRACT

A set of vertices W is a resolving set of a graph G if every two vertices of G have distinct representations of distances with respect to the set W. The number of vertices in a smallest resolving set is called the metric dimension. This invariant has extensive applications in robotics, since the metric dimension can represent the minimum number of landmarks, which uniquely determine the position of a robot moving in a graph space. Finding the metric dimension of a graph is a non-deterministic polynomial-time hard problem. We present exact values of the metric dimension of several networks, which can be obtained as categorial products of graphs.

KEYWORDS:

• metric dimension
• resolving set
• categorial product
• robotics

2010 AMS SUBJECT CLASSIFICATIONS:

• 05C12
• 05C35
• 68R10

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

The work of the first author has been supported by the National Research Foundation of South Africa; Grant numbers: [91499, 90793].