The metric dimension of comb product graphs

Abstract

Throughout this paper, all graphs G are finite, connected, and simple. We denote by V the vertex set of G and by E the edge set of G. The distance between two vertices u, v ∈ V (G), denoted by d (u, v), is the length of a shortest path from u to v in G. Let W = {w1, w2, . . . , wk} be an ordered subset of V (G). The representation of a vertex v of G with respect to W is defined as the k-tuple r (v|W ) = (d (v, w1) , d(v, w2), . . . , d (v, wk)). The set W is called a resolving set of G if every two distinct vertices x, y ∈ V (G) satisfy r (x|W ) = r (y|W ). A basis of G is a resolving set of G with the minimum cardinality, and the metric dimension of G refers to its cardinality and is denoted by β (G). The metric dimension problems were first studied by Harary and Melter [4]. Khuller et al. [5] studied the metric dimension motivated by the robot navigation in a graph space. A resolving set for a graph corresponds to the presence of distinctively labelled “landmark” nodes in the graph. It is assumed that a robot can detect the distance to each node of the landmarks, and hence uniquely determine its location in the graph. Garey and Johnson [3] showed that determining the metric dimension of an arbitrary graph is an NP-complete problem. However, Chartrand et al. [2] have obtained some results as follows.