Fault-Tolerant Path-Embedding of Twisted Hypercube-Like Networks ( THLNs )

Huifeng Zhang, Xirong Xu, Qiang Zhang and Yuansheng Yang
Additional contact information
Huifeng Zhang: School of Computer Science and Technology, Dalian University of Technology, Dalian 116024, China
Xirong Xu: School of Computer Science and Technology, Dalian University of Technology, Dalian 116024, China
Qiang Zhang: School of Computer Science and Technology, Dalian University of Technology, Dalian 116024, China
Yuansheng Yang: School of Computer Science and Technology, Dalian University of Technology, Dalian 116024, China

Mathematics, 2019, vol. 7, issue 11, 1-10

Abstract: It is known widely that an interconnection network can be denoted by a graph G = ( V , E ) , where V denotes the vertex set and E denotes the edge set. Investigating structures of G is necessary to design a suitable topological structure of interconnection network. One of the critical issues in evaluating an interconnection network is graph embedding, which concerns whether a host graph contains a guest graph as its subgraph. Linear arrays (i.e., paths) and rings (i.e., cycles) are two ordinary guest graphs (or basic networks) for parallel and distributed computation. In the process of large-scale interconnection network operation, it is inevitable that various errors may occur at nodes and edges. It is significant to find an embedding of a guest graph into a host graph where all faulty nodes and edges have been removed. This is named as fault-tolerant embedding. The twisted hypercube-like networks ( T H L N s ) contain several important hypercube variants. This paper is concerned with the fault-tolerant path-embedding of n -dimensional ( n - D ) T H L N s . Let G n be an n - D T H L N and F be a subset of V ( G n ) ∪ E ( G n ) with | F | ≤ n − 2 . We show that for two different arbitrary correct vertices u and v , there is a faultless path P u v of every length l with 2 n − 1 − 1 ≤ l ≤ 2 n − f v − 1 − α , where α = 0 if vertices u and v form a normal vertex-pair and α = 1 if vertices u and v form a weak vertex-pair in G n − F ( n ≥ 5 ).

Keywords: combinatorics; multiprocessor interconnection networks; computer network reliability; network topology; hypercubes; twisted hypercube-like networks THLNs; fault tolerance; path-embedding (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/11/1066/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/11/1066/ (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:7:y:2019:i:11:p:1066-:d:284219

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 ().