Cycle Existence for All Edges in Folded Hypercubes under Scope Faults

Che-Nan Kuo and Yu-Huei Cheng ()
Additional contact information
Che-Nan Kuo: Department of Artificial Intelligence, CTBC Financial Management College, Tainan 709, Taiwan
Yu-Huei Cheng: Department of Information and Communication Engineering, Chaoyang University of Technology, Taichung 413, Taiwan

Mathematics, 2023, vol. 11, issue 15, 1-14

Abstract: The reliability of large-scale networks can be compromised by various factors such as natural disasters, human-induced incidents such as hacker attacks, bomb attacks, or even meteorite impacts, which can lead to failures in scope of processors or links. Therefore, ensuring fault tolerance in the interconnection network is vital to maintaining system reliability. The n -dimensional folded hypercube network structure, denoted as F Q n , is constructed by adding an edge between every pair of vertices with complementary addresses from an n -dimensional hypercube, Q n . Notably, F Q n exhibits distinct characteristics based on the dimensionality: it is bipartite for odd integers n ≥ 3 and non-bipartite for even integers n ≥ 2 . Recently, in terms of the issue of how F Q n performs in communication under regional or widespread destruction, we mentioned that in F Q n , even when a pair of adjacent vertices encounter errors, any fault-free edge can still be embedded in cycles of various lengths. Additionally, even when the smallest communication ring experiences errors, it is still possible to embed cycles of any length. The smallest communication ring in F Q n is observed to be the four-cycle ring. In order to further investigate the communication capabilities of F Q n , we further discuss whether every fault-free edge will still be a part of every communication ring with different lengths when the smallest communication ring is compromised in F Q n . In this study, we consider a fault-free edge e = ( u , v ) and F 4 = { f 1 , f 2 , f 3 , f 4 } as the set of faulty extreme vertices for any four cycles in F Q n . Our research focuses on investigating the cycle-embedding properties in F Q n − F 4 , where the fault-free edges play a significant role. The following properties are demonstrated: (1) For n ≥ 4 in F Q n − F 4 , every even length cycle with a length ranging from 4 t o 2 n − 4 contains a fault-free edge e ; (2) For every even n ≥ 4 in F Q n − F 4 , every odd length cycle with a length ranging from n + 1 t o 2 n − 5 contains a fault-free edge e . These findings provide insights into the cycle-embedding capabilities of F Q n , specifically in the context of fault tolerance when considering certain sets of faulty vertices.

Keywords: graph theory; interconnection networks; reliability; scope faults; folded hypercubes (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/15/3391/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/15/3391/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:15:p:3391-:d:1209866

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().