TY - JOUR

T1 - Fault-Tolerant Metric Dimension of Interconnection Networks

AU - Hayat, Sakander

AU - Khan, Asad

AU - Malik, Muhammad Yasir Hayat

AU - Imran, Muhammad

AU - Siddiqui, Muhammad Kamran

N1 - Funding Information:
The work of Sakander Hayat and Muhammad Imran was supported by the University Programme for Advance Research (UPAR) grant of United Arab Emirates University under Grant G00003271.
Publisher Copyright:
© 2013 IEEE.

PY - 2020

Y1 - 2020

N2 - A fixed interconnection parallel architecture is characterized by a graph, with vertices corresponding to processing nodes and edges representing communication links. An ordered set R of nodes in a graph G is said to be a resolving set of G if every node in G is uniquely determined by its vector of distances to the nodes in R. Each node in R can be thought of as the site for a sonar or loran station, and each node location must be uniquely determined by its distances to the sites in R. A fault-tolerant resolving set R for which the failure of any single station at node location v in R leaves us with a set that still is a resolving set. The metric dimension (resp. fault-tolerant metric dimension) is the minimum cardinality of a resolving set (resp. fault-tolerant resolving set). In this article, we study the metric and fault-tolerant dimension of certain families of interconnection networks. In particular, we focus on the fault-tolerant metric dimension of the butterfly, the Benes and a family of honeycomb derived networks called the silicate networks. Our main results assert that three aforementioned families of interconnection have an unbounded fault-tolerant resolvability structures. We achieve that by determining certain maximal and minimal results on their fault-tolerant metric dimension.

AB - A fixed interconnection parallel architecture is characterized by a graph, with vertices corresponding to processing nodes and edges representing communication links. An ordered set R of nodes in a graph G is said to be a resolving set of G if every node in G is uniquely determined by its vector of distances to the nodes in R. Each node in R can be thought of as the site for a sonar or loran station, and each node location must be uniquely determined by its distances to the sites in R. A fault-tolerant resolving set R for which the failure of any single station at node location v in R leaves us with a set that still is a resolving set. The metric dimension (resp. fault-tolerant metric dimension) is the minimum cardinality of a resolving set (resp. fault-tolerant resolving set). In this article, we study the metric and fault-tolerant dimension of certain families of interconnection networks. In particular, we focus on the fault-tolerant metric dimension of the butterfly, the Benes and a family of honeycomb derived networks called the silicate networks. Our main results assert that three aforementioned families of interconnection have an unbounded fault-tolerant resolvability structures. We achieve that by determining certain maximal and minimal results on their fault-tolerant metric dimension.

KW - Graph theory

KW - NP-complete problems

KW - fault-tolerant metric dimension

KW - interconnection networks

KW - metric dimension

UR - http://www.scopus.com/inward/record.url?scp=85090288051&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85090288051&partnerID=8YFLogxK

U2 - 10.1109/ACCESS.2020.3014883

DO - 10.1109/ACCESS.2020.3014883

M3 - Article

AN - SCOPUS:85090288051

SN - 2169-3536

VL - 8

SP - 145435

EP - 145445

JO - IEEE Access

JF - IEEE Access

M1 - 9162022

ER -