Fault-tolerant metric and partition dimension of graphs
Abstract
Abstract. A set W of vertices in a graph G is called a resolving set for G if for every pair of distinct vertices u and v of G there exists a vertex w 6 W such that the distance between u and w is different from the distance between v and w. The cardinality of a minimum resolving set is called the metric dimension of G, denoted by β(G). A resolving set W for G is fault-tolerant if W'\{w}, for each w in W, is also a resolving set and the fault-tolerant metric dimension of G is the minimum cardinality of such a set, denoted by β (G). We characterize all the graphs G such that β'(G) - β'(G) = 1. A κ-partition = {S1, S2,..., Sk,} of V(G) is resolving if for every pair of distinct vertices u, v in G, there is a set Si in Π so that the minimum distance between u and a vertex of Si is different from the minimum distance between v and a vertex of Si. A resolving partition Π is fault-tolerant if for every pair of distinct vertices u and v in V(G), there are at least two sets Si, Sj in Π so that the minimum distance between u and a vertex of Si and a vertex of Sj is different from the minimum distance between v and a vertex of Si and a vertex of Sj. The cardinality of a minimum fault-tolerant resolving partition is called the fault-tolerant partition dimension, denoted by P(G). In this paper, we show that every pair a,b of positive integers with 6 ≥ 6 and [b/2] +1 ≤ a ≤ b - 2 is realizable as the fault-tolerant metric dimension and the fault-tolerant partition dimension of some connected graphs. Also, we show that P(G) = n if and only if G = Kn or G = K n - e.
