Fault-tolerance in resolvability. (English) Zbl 1197.05041

Javaid, Imran; Salman, Muhammad; Chaudhry, Muhammad Anwar; Shokat, Sara

Util. Math. 80, 263-275 (2009).

Summary: A subset \(W= \{w1,\dots,w_k\}A\) of vertices of a graph \(G\) is called a resolving set for \(G\) if for every two distinct vertices \(x,y\in V(G)\) there is a vertex \(w_i\in W\) such that \(d(x,w_i)\neq d(y,w_i)\). A resolving set \(W\) for \(G\) is fault-tolerant if \(W\setminus\{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 \(\beta'(G)\). A \(k\)-partition \(\Pi=\{S_1,S_2,\dots, S_k\}\) of \(V(G)\) is said to be fault-tolerant resolving if the codes \(c_\Pi(v)\), \(v\in V(G)\), differ by at least two coordinates where \(c_\Pi(v)= (d(v,S_1),d(v,S_2),\dots,d(v,S_k))\). The minimum \(k\) for which there is a fault-tolerant resolving \(k\)-partition of \(V(G)\) is called the fault-tolerant partition dimension of \(G\), denoted by \({\mathcal P}(G)\). In this paper, we study fault-tolerant metric dimension and fault-tolerant partition dimension of graphs and their relationship. We show that every pair \(a, b\) \((a\neq b-1)\) of positive integers with \(5\leq a\leq b\) is realizable as the fault-tolerant metric dimension and the fault-tolerant partition dimension for some connected graphs. Also, bounds on maximum order of a graph \(G\) are presented in terms of diameter, fault-tolerant metric dimension and fault-tolerant partition dimension of \(G\).

MSC:

05C12

Distance in graphs

Keywords:

metric dimension; fault-tolerant metric dimension; partition dimension; fault-tolerant partition dimension; diameter; pumpkin graph; square grid