Hamiltonian fault-tolerance of hypercubes

DOI10.1016/j.endm.2007.07.074zbMath1341.05142OpenAlexW1997928449MaRDI QIDQ3503505

Tomáš Dvořák, Petr Gregor

Publication date: 5 June 2008

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2007.07.074

zbMATH Keywords

hypercubeNP-completenesspath partitionHamiltonian fault-tolerance

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Eulerian and Hamiltonian graphs (05C45)

Related Items (5)

Extending perfect matchings to Gray codes with prescribed ends ⋮ Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges ⋮ Hamiltonian laceability in hypercubes with faulty edges ⋮ Long paths and cycles in hypercubes with faulty vertices ⋮ Embedding Hamiltonian cycles in alternating group graphs under conditional fault model

Cites Work

• Unnamed Item
• Fault-tolerant cycle embedding in the hypercube
• Longest fault-free paths in hypercubes with vertex faults
• Hyper-Hamilton laceable and caterpillar-spannable product graphs
• Linear array and ring embeddings in conditional faulty hypercubes
• Fault-tolerant Hamiltonian laceability of hypercubes.
• Spanning multi-paths in hypercubes
• Perfect matchings extend to Hamilton cycles in hypercubes
• Partitions of Faulty Hypercubes into Paths with Prescribed Endvertices
• On the Existence of Hamiltonian Circuits in Faulty Hypercubes
• Hamiltonian Cycles with Prescribed Edges in Hypercubes

This page was built for publication: Hamiltonian fault-tolerance of hypercubes