Long paths and cycles in hypercubes with faulty vertices

DOI10.1016/j.ins.2009.06.011zbMath1193.68052OpenAlexW2071314276MaRDI QIDQ730940

Petr Gregor, Jiří Fink

Publication date: 1 October 2009

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ins.2009.06.011

zbMATH Keywords

hypercubelong cyclelong pathfaulty vertex

Mathematics Subject Classification ID

Applications of graph theory (05C90) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items

Rounds in combinatorial search ⋮ Edge-fault-tolerant diameter and bipanconnectivity of hypercubes ⋮ Long cycles in hypercubes with optimal number of faulty vertices ⋮ Paired many-to-many disjoint path covers in faulty hypercubes ⋮ Conditional edge-fault pancyclicity of augmented cubes ⋮ Conditional edge-fault-tolerant Hamiltonicity of dual-cubes ⋮ Hamiltonian laceability in hypercubes with faulty edges ⋮ Edge-fault-tolerant panconnectivity and edge-pancyclicity of the complete graph ⋮ Efficient Connectivity Testing of Hypercubic Networks with Faults ⋮ Paired 2-disjoint path covers and strongly Hamiltonian laceability of bipartite hypercube-like graphs ⋮ Hamiltonian cycles in hypercubes with faulty edges ⋮ Fault-tolerant edge-bipancyclicity of faulty hypercubes under the conditional-fault model ⋮ Many-to-many disjoint paths in hypercubes with faulty vertices ⋮ Independent spanning trees on even networks ⋮ Computational complexity of long paths and cycles in faulty hypercubes ⋮ Conditional edge-fault Hamiltonicity of augmented cubes ⋮ Pancyclicity and bipancyclicity of conditional faulty folded hypercubes ⋮ Long paths in hypercubes with a quadratic number of faults ⋮ Hamiltonian properties on a class of circulant interconnection networks

Cites Work

• On ring embedding in hypercubes with faulty nodes and links
• Fault-tolerant cycle embedding in the hypercube
• Embedding a ring in a hypercube with both faulty links and faulty nodes
• Longest fault-free paths in hypercubes with vertex faults
• Cycles embedding in hypercubes with node failures
• Path embedding in faulty hypercubes
• Edge-fault-tolerant bipanconnectivity of hypercubes
• Long paths in hypercubes with conditional node-faults
• Conditional edge-fault-tolerant edge-bipancyclicity of hypercubes
• Hamiltonian fault-tolerance of hypercubes
• Edge Multiplicity and Other Trace Functions
• A Survey of Combinatorial Gray Codes
• Embedded paths and cycles in faulty hypercubes