On the metric dimension of the folded n-cube

Research paper by Yuezhong Zhang, Lihang Hou, Bo Hou, Weili Wu, Ding-Zhu Du, Suogang Gao

Indexed on: 06 Nov '20Published on: 09 Sep '19Published in: Optimization Letters


A subset S of vertices in a graph G is called a resolving set for G if for arbitrary two distinct vertices \(u, v\in V\), there exists a vertex x from S such that the distances \(d(u, x)\ne d(v, x)\). The metric dimension of G is the minimum cardinality of a resolving set of G. A minimal resolving set is a resolving set which has no proper subsets that are resolving sets. Let \(\Box _{n}\) denote the folded n-cube. In this paper, we consider the metric dimension of \(\Box _{n}\). By constructing explicitly minimal resolving sets for \(\Box _{n}\), we obtain upper bounds on the metric dimension of this graph.