Complexity analysis and algorithmic approaches to the dominant metric dimension problem: a case study of fullerene graphs

The dominant metric dimension is the minimum cardinality of a subset of vertices in a graph that is both a resolving set and a dominating set, where a resolving set is a subset of vertices whose distance vectors uniquely identify all vertices of the graph, and a dominating set is a subset of vertices such that every vertex outside the set is adjacent to at least one vertex in the set. In this paper, in addition to proving the NP-hardness of the dominant metric dimension problem, we present a linear model and a tabu search-based approximation algorithm for computing this parameter. The proposed algorithm is implemented on fullerene graphs.