Hamiltonian connectivity of restricted hypercube-like networks under the conditional fault model

DOI10.1016/J.TCS.2012.11.034MaRDI QIDQ1939253zbMATH OpenOpenAlexFDO

Authors Qiang Dong, Junlin Zhou, Yan Fu, Hui Gao

Publication date 4 March 2013

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.5391

zbMATH Keywords

conditional fault modelfault toleranceHamiltonian pathhypercube-like networkinterconnection networksnear-Hamiltonian path

Mathematics Subject Classification ID

Mathematical problems of computer architecture (68M07) Network design and communication in computer systems (68M10) Reliability, testing and fault tolerance of networks and computer systems (68M15) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Twisted hypercube-like networks (THLNs) are an important class of interconnection networks for parallel computing systems, which include most popular variants of the hypercubes, such as crossed cubes, M"obius cubes, twisted cubes and locally twisted cubes. This paper deals with the fault-tolerant hamiltonian connectivity of THLNs under the large fault model. Let $G$ be an $n$-dimensional THLN and $$, where $ngeq7$ and $|F|leq2n-10$. We prove that for any two nodes $u,vinV(G-F)$ satisfying a simple necessary condition on neighbors of $u$ and $v$, there exists a hamiltonian or near-hamiltonian path between $u$ and $v$ in $G-F$. The result extends further the fault-tolerant graph embedding capability of THLNs.

Recommendations

• Conditional edge-fault Hamiltonian-connectivity of restricted hypercube-like networks
• Hamiltonicity of Matching Composition Networks with Conditional Edge Faults
• Hamiltonian properties of twisted hypercube-like networks with more faulty elements
• Pancyclicity of restricted hypercube-like networks under the conditional fault model
• On conditional fault tolerance of hierarchical cubic networks

Cited in

(13)

• Hamiltonian connectivity of the WK-recursive network with faulty nodes
• Hamiltonicity of the hierarchical cubic network
• Conditional edge-fault-tolerant Hamiltonicity of the data center network
• Proof that pyramid networks are 1-Hamiltonian-connected with high probability
• Conditional edge-fault Hamiltonian-connectivity of restricted hypercube-like networks
• Hamiltonicity of Matching Composition Networks with Conditional Edge Faults
• Fault-tolerant hamiltonicity and fault-tolerant hamiltonian connectivity of the folded Petersen cube networks
• Fault Hamiltonicity and fault Hamiltonian-connectivity of generalised matching networks
• A computer-aided examination of some classes of hypercube-like super fault-tolerant Hamiltonian networks
• Hamiltonian properties of twisted hypercube-like networks with more faulty elements
• Unpaired Many-to-Many Disjoint Path Cover of Balanced Hypercubest
• Strong Menger connectivity with conditional faults on the class of hypercube-like networks
• Hamiltonian connectivity and globally \(3^*\)-connectivity of dual-cube extensive networks

This page was built for publication: Hamiltonian connectivity of restricted hypercube-like networks under the conditional fault model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1939253)