Spanning multi-paths in hypercubes

DOI10.1016/j.disc.2005.12.050zbMath1125.05054OpenAlexW2081508499MaRDI QIDQ2370445

Rostislav Caha, Václav Koubek

Publication date: 26 June 2007

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

Full work available at URL: https://doi.org/10.1016/j.disc.2005.12.050

zbMATH Keywords

hypercubeHamiltonian pathpath partitionspanning paths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Related Items (20)

A type of perfect matchings extend to Hamiltonian cycles in \(k\)-ary \(n\)-cubes ⋮ Edge-fault-tolerant diameter and bipanconnectivity of hypercubes ⋮ Paired many-to-many disjoint path covers in faulty hypercubes ⋮ Hamiltonian fault-tolerance of hypercubes ⋮ Matchings extend to Hamiltonian cycles in 5-cube ⋮ Paired many-to-many disjoint path covers of the hypercubes ⋮ Unnamed Item ⋮ The 2-path-bipanconnectivity of hypercubes ⋮ Generalized Gray codes with prescribed ends ⋮ Path partitions of hypercubes ⋮ Disjoint paths in hypercubes with prescribed origins and lengths ⋮ On generalized middle-level problem ⋮ Unpaired many-to-many vertex-disjoint path covers of a class of bipartite graphs ⋮ Many-to-many disjoint paths in faulty hypercubes ⋮ Hamiltonicity of hypercubes with faulty vertices ⋮ Small matchings extend to Hamiltonian cycles in hypercubes ⋮ Fault-free Hamiltonian cycle including given edges in folded hypercubes with faulty edges ⋮ Paired many-to-many disjoint path covers of hypercubes with faulty edges ⋮ Many-to-many \(n\)-disjoint path covers in \(n\)-dimensional hypercubes ⋮ Path coverings with prescribed ends in faulty hypercubes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Spanning regular caterpillars in hypercubes
• Embedding ladders and caterpillars into the hypercube
• On paths and cycles dominating hypercubes
• Hamiltonian paths with prescribed edges in hypercubes
• The number of caterpillars
• On Hamiltonian circuits and spanning trees of hypercubes
• Embedding Trees in a Hypercube is NP-Complete
• One-legged caterpillars span hypercubes
• Embedding $m$-quasistars into $n$-cubes
• On Oriented Embedding of the Binary Tree into the Hypercube
• On cubes and dichotomic trees
• Embedding the polytomic tree into the $n$-cube
• Spanning caterpillars of a hypercube
• Optimal embeddings of generalized ladders into hypercubes
• Embedding complete trees into the hypercube
• Optimal embeddings of odd ladders into a hypercube

This page was built for publication: Spanning multi-paths in hypercubes