Fault-tolerant metric dimension of graphs

Abstract

An ordered set S of vertices in a graph G is said to resolve G if every vertex in G is uniquely determined by its vector of distances to the vertices in S. The metric dimension of G is the minimum cardinality of a resolving set of G. In this paper we introduce the study of the fault-tolerant metric dimension of a graph. A resolving set S for G is fault-tolerant if S n fvg is also a resolving set, for each v in S, and the fault-tolerant metric dimension of G is the minimum cardinality of such a set. In this paper we characterize the fault-tolerant resolving sets in a tree T. We show that the fault-tolerant metric dimension values are bounded by a function of the metric dimension values independent of any graphs.