A new lower bound for the doubly metric dimension and related extremal differences

Abstract

In this paper a new graph invariant based on the minimum hitting set problem is introduced.
It is shown that it represents a tight lower bound for the doubly metric dimension of 
a graph. Exact values of this new invariant for paths, cycles, stars, complete graphs and
complete bipartite graphs are obtained. The paper analyzes certain tight bounds 
for the new invariant in general case. Also, several extremal differences 
between some related invariants are determined.