On fault-tolerant partition dimension of graphs

Abstract

Fault-tolerant resolving partition is natural extension of resolving partitions which have many applications in different areas of computer sciences for example sensor networking, intelligent systems, optimization and robot navigation. For a nontrivial connected graph G (V (G) , E (G)), the partition representation of vertex v with respect to an ordered partition Π = {S _i  : 1 ≤ i ≤ k} of V (G) is the k-vector $r\left(v\right|\Pi )=(d(v,S_i){)}_{i=1}^k$ , where, d (v, S _i ) = min {d (v, x) |x ∈ S _i }, for i ∈ {1, 2, …, k}. A partition Π is said to be fault-tolerant partition resolving set of G if r (u|Π) and r (v|Π) differ by at least two places for all u ≠ v ∈ V (G). A fault-tolerant partition resolving set of minimum cardinality is called the fault-tolerant partition basis of G and its cardinality the fault-tolerant partition dimension of G denoted by $\mathcal{P}\left(\mathcal{G}\right)$ . In this article, we will compute fault-tolerant partition dimension of families of tadpole and necklace graphs.