Fault-tolerant basis of generalized fat trees and perfect binary tree derived architectures

0585137 - ÚI 2025 DE eng J - Journal Article
Prabhu, S. - Manimozhi, V. - Davoodi, Akbar - García Guirao, J. L.
Fault-tolerant basis of generalized fat trees and perfect binary tree derived architectures.
Journal of Supercomputing. Online First 06 April 2024 (2024). ISSN 0920-8542. E-ISSN 1573-0484
Institutional support: RVO:67985807
Keywords : Basis * Fault-tolerant basis * Twin vertices * Generalized fat tree * Perfect binary trees
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impact factor: 3.3, year: 2022
Method of publishing: Limited access
https://doi.org/10.1007/s11227-024-06053-5

The ability to uniquely identify all nodes in a network based on network distances has proven to be highly beneficial despite the computational challenges involved in discovering minimal resolving sets within an interconnection network.
A subset $R$ of vertices of a graph $G$ is referred to as a resolving set of the graph if each node can be uniquely identified by its distance code with respect to $R$, with its minimal cardinality defining the metric dimension of $G$. Similarly, a resolving set $F \subseteq V$ is designated as a fault-tolerant resolving set if $F \setminus \{s\}$ serves as a resolving set for each $s \in F$. The minimum cardinality of $F$ represents the fault-tolerant metric dimension of $G$. Although determining the precise metric dimension of a given graph remains challenging, various effective techniques and meaningful constraints have been developed for different graph families. However, no notable technique has been developed to find fault-tolerant metric dimension of a given graph. Recently, Prabhu et al. have shown that each twin vertex of $G$ belongs to every fault-tolerant resolving set of $G$. Consequently, the fault-tolerant metric dimension is equal to the order of the graph $G$ if and only if each vertex of $G$ is a twin vertex, a characterization proved in [Appl. Math. Comput. \textbf{420} (2022) 126897] corrects a wrong characterization in the literature. It is also interesting to note from the above literature correction that the twin vertices are necessary to form the fault-tolerant resolving set, but determining whether they are sufficient is challenging. Evidence of this context is also discussed in this paper through the amalgamation of perfect binary trees. This article focuses on determining the exact value of the fault-tolerant metric dimension of generalized fat trees. For the amalgamation of perfect binary trees, both the metric dimension and fault-tolerant metric dimension were precisely found.
Permanent Link: https://hdl.handle.net/11104/0352872