All metric bases and fault-tolerant metric dimension for square of grid

Laxman Saha
Mithun Basak
Kalishankar Tiwary

Abstract. For a simple connected graph \(G=(V,E)\) and an ordered subset \(W = \{w_1,w_2,\ldots, w_k\}\) of \(V\), the code of a vertex \(v\in V\), denoted by \(\mathrm{code}(v)\), with respect to \(W\) is a \(k\)-tuple \((d(v,w_1),\ldots, d(v, w_k))\), where \(d(v, w_t)\) represents the distance between \(v\) and \(w_t\). The set \(W\) is called a resolving set of \(G\) if \(\mathrm{code}(u)\neq \mathrm{code}(v)\) for every pair of distinct vertices \(u\) and \(v\). A metric basis of \(G\) is a resolving set with the minimum cardinality. The metric dimension of \(G\) is the cardinality of a metric basis and is denoted by \(\beta(G)\). A set \(F\subset V\) is called fault-tolerant resolving set of \(G\) if \(F\setminus{\{v\}}\) is a resolving set of \(G\) for every \(v\in F\). The fault-tolerant metric dimension of \(G\) is the cardinality of a minimal fault-tolerant resolving set. In this article, a complete characterization of metric bases for \(G_{mn}^2\) has been given. In addition, we prove that the fault-tolerant metric dimension of \(G_{mn}^2\) is 4 if \(m+n\) is even. We also show that the fault-tolerant metric dimension of \(G_{mn}^2\) is at least 5 and at most 6 when \(m+n\) is odd.

Keywords: code, resolving set, metric dimension, fault-tolerant resolving set, fault-tolerant metric dimension.

Mathematics Subject Classification: 05C12, 05C05, 05C90, 05C76.

Full text (pdf)