Fault-free Hamiltonian cycles in balanced hypercubes with conditional edge faults

DOI10.1142/S0129054119500175MaRDI QIDQ5205025zbMATH OpenOpenAlexWikidataFDO

Authors Pingshan Li, Min Xu

Publication date 10 December 2019

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

balanced hypercubesfault-toleranceHamiltonian cycleshypercubes

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Reliability, testing and fault tolerance of networks and computer systems (68M15) Graph theory (including graph drawing) in computer science (68R10)

Abstract: The balanced hypercube, $B{H}_n$, is a variant of hypercube $Q_n$. Zhou et al. [Inform. Sci. 300 (2015) 20-27] proposed an interesting problem that whether there is a fault-free Hamiltonian cycle in $B{H}_n$ with each vertex incident to at least two fault-free edges. In this paper, we consider this problem and show that each fault-free edge lies on a fault-free Hamiltonian cycle in $B{H}_n$ after no more than $4n-5$ faulty edges occur if each vertex is incident with at least two fault-free edges for all $nge2$. Our result is optimal with respect to the maximum number of tolerated edge faults.

Recommendations

• Hamiltonian cycles of balanced hypercube with more faulty edges
• Hamiltonian cycle embedding for fault tolerance in balanced hypercubes
• Fault-tolerance of balanced hypercubes with faulty vertices and faulty edges.
• Edge-fault-tolerant edge-bipancyclicity of balanced hypercubes
• Cycles embedding in balanced hypercubes with faulty edges and vertices

Cites work

• A fault-free Hamiltonian cycle passing through prescribed edges in a hypercube with faulty edges
• Bipanconnectivity of balanced hypercubes
• Conditional edge-fault Hamiltonicity of augmented cubes
• Conditional edge-fault-tolerant Hamiltonicity of dual-cubes
• Edge disjoint paths in hypercubes and folded hypercubes with conditional faults
• Edge-fault-tolerant bipanconnectivity of hypercubes
• Edge-fault-tolerant edge-bipancyclicity of balanced hypercubes
• Edge-fault-tolerant pancyclicity of arrangement graphs
• Edge-fault-tolerant properties of hypercubes and folded hypercubes
• Edge-pancyclicity and Hamiltonian laceability of the balanced hypercubes
• Fault-free Hamiltonian cycles in crossed cubes with conditional link faults
• Fault-tolerant edge-bipancyclicity of faulty hypercubes under the conditional-fault model
• Fault-tolerant embedding of paths in crossed cubes
• Fault-tolerant Hamiltonian laceability of balanced hypercubes
• Fault-tolerant Hamiltonian laceability of Cayley graphs generated by transposition trees
• Hamiltonian cycle embedding for fault tolerance in balanced hypercubes
• Hamiltonian cycles in hypercubes with faulty edges
• Matching preclusion for balanced hypercubes
• On embedding cycles into faulty twisted cubes
• Strong Menger connectivity with conditional faults of folded hypercubes
• Super connectivity of balanced hypercubes
• Survey on path and cycle embedding in some networks
• Symmetric Property and Reliability of Balanced Hypercube
• Two node-disjoint paths in balanced hypercubes
• Various cycles embedding in faulty balanced hypercubes
• Vertex-fault-tolerant cycles embedding in balanced hypercubes

Cited in

(14)

• Cycles embedding in balanced hypercubes with faulty edges and vertices
• Edge-disjoint Hamiltonian cycles of balanced hypercubes
• Edge-fault-tolerant edge-bipancyclicity of balanced hypercubes
• Fault-free Hamiltonian paths passing through prescribed linear forests in balanced hypercubes with faulty links
• Fault-free Hamilton cycles in burnt pancake graphs with conditional edge faults
• Hamiltonian cycles of balanced hypercube with more faulty edges
• Hamiltonian cycle embedding for fault tolerance in balanced hypercubes
• Fault-tolerance of balanced hypercubes with faulty vertices and faulty edges.
• An Efficient Algorithm for Embedding Two-Dimensional Tori into Balanced Hypercubes
• Enhancing fault tolerance of balanced hypercube networks by the edge partition method
• Hamiltonian cycles of balanced hypercube with disjoint faulty edges
• Edge-fault-tolerant edge-bipancyclicity of modified bubble-sort graphs
• A note on fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges
• A fault-free Hamiltonian cycle passing through prescribed edges in a hypercube with faulty edges

This page was built for publication: Fault-free Hamiltonian cycles in balanced hypercubes with conditional edge faults

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