Twin vertices in fault-tolerant metric sets and fault-tolerant metric dimension of multistage interconnection networks

• Published in: Applied mathematics and computation 2022-05, Vol.420, p.126897, Article 126897
• Main Authors: Prabhu, S., Manimozhi, V., Arulperumjothi, M., Klavžar, Sandi
• Format: Article
• Language: English
• Subjects: Benes network; Butterfly network; Fault-tolerant metric dimension; Metric dimension; Silicate network; Twin vertex
• ISSN: 0096-3003; 1873-5649
• DOI: 10.1016/j.amc.2021.126897

•The fault-tolerant metric dimension is determined for Butterfly networks, Benes networks, and silicate networks. This extends known partial results and disproves related conjectures from [IEEE Access 8 (2020) 145435–145445].•A characterization of graphs with largest possible fault-tolerant metric dimension is clarified. This correct an error from [Mathematics 7(1) (2019) 78]. A set of vertices S⊆V(G) is a resolving set of a graph G if for each x,y∈V(G) there is a vertex u∈S such that d(x,u)≠d(y,u). A resolving set S is a fault-tolerant resolving set if S∖{x} is a resolving set for every x∈S. The fault-tolerant metric dimension (FTMD) β′(G) of G is the minimum cardinality of a fault-tolerant resolving set. It is shown that each twin vertex of G belongs to every fault-tolerant resolving set of G. As a consequence, β′(G)=n(G) iff each vertex of G is a twin vertex, which corrects a wrong characterization of graphs G with β′(G)=n(G) from [Mathematics 7(1) (2019) 78]. This FTMD problem is reinvestigated for Butterfly networks, Benes networks, and silicate networks. This extends partial results from [IEEE Access 8 (2020) 145435–145445], and at the same time, disproves related conjectures from the same paper. Dedicated to Dr. Bharati Rajan on her 70th birthday