Hamiltonian paths with prescribed edges in hypercubes
From MaRDI portal
The Caha-Koubek condition states that any proper subset \(S\) of edges of a Hamiltonian path between \(u\) and \(v\) necessarily induces a subgraph \(P\) consisting of pairwise vertex-disjoint paths such that \(P\) contains no path between \(u\) and \(v\), and neither \(u\) nor \(v\) is incident with more than one edge of \(S\). The authors show that given vertices \(u\) and \(v\) with the distance between \(u\) and \(v\) being odd, and a set of at most \(2n-4\) prescribed edges of the \(n\)-dimensional hypercube satisfying the Caha-Koubek condition, there exists a Hamiltonian path between \(u\) and \(v\) passing through every edge of the prescribed set. The results are shown to relate to the classical problem of Hamiltonicity of hypercubes with faulty edges.
Recommendations
- Hamiltonian Cycles with Prescribed Edges in Hypercubes
- Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets
- Hamiltonicity of hypercubes with a constraint of required and faulty edges
- A fault-free Hamiltonian cycle passing through prescribed edges in a hypercube with faulty edges
- Hamiltonian cycles and paths in hypercubes with disjoint faulty edges
Cites work
- A Survey of Combinatorial Gray Codes
- A survey of the theory of hypercube graphs
- Fault-tolerant Hamiltonian laceability of hypercubes.
- Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets
- Hamiltonian Cycles with Prescribed Edges in Hypercubes
- scientific article; zbMATH DE number 52113 (Why is no real title available?)
- On Hamiltonian circuits and spanning trees of hypercubes
- On ring embedding in hypercubes with faulty nodes and links
- On the Existence of Hamiltonian Circuits in Faulty Hypercubes
- Parallel concepts in graph theory
Cited in
(39)- A type of perfect matchings extend to Hamiltonian cycles in \(k\)-ary \(n\)-cubes
- Extending perfect matchings to Gray codes with prescribed ends
- Hamiltonian paths passing through prescribed edges in balanced hypercubes
- Embedding fault-free Hamiltonian paths with prescribed linear forests into faulty ternary \(n\)-cubes
- Fault-free Hamiltonian paths passing through prescribed linear forests in balanced hypercubes with faulty links
- Matchings extend to Hamiltonian cycles in hypercubes with faulty edges
- Fault-free Hamiltonian cycles passing through a prescribed linear forest in 3-ary \(n\)-cube with faulty edges
- Many-to-many two-disjoint path covers in cylindrical and toroidal grids
- Spanning multi-paths in hypercubes
- Hamiltonian paths and cycles pass through prescribed edges in the balanced hypercubes
- Many-to-many two-disjoint path covers in restricted hypercube-like graphs
- Disjoint path covers in cubes of connected graphs
- scientific article; zbMATH DE number 434488 (Why is no real title available?)
- scientific article; zbMATH DE number 3884208 (Why is no real title available?)
- Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets
- scientific article; zbMATH DE number 6513170 (Why is no real title available?)
- Fault-free Hamiltonian cycles passing through a linear forest in ternary n-cubes with faulty edges
- Bipanconnectivity of faulty hypercubes with minimum degree
- Fault-free Hamiltonian cycle including given edges in folded hypercubes with faulty edges
- Paired 2-disjoint path covers and strongly Hamiltonian laceability of bipartite hypercube-like graphs
- Hamiltonian laceability of hypercubes without isometric subgraphs
- Embedding various cycles with prescribed paths into \(k\)-ary \(n\)-cubes
- Hamiltonian Cycles with Prescribed Edges in Hypercubes
- Hamiltonian paths and cycles with prescribed edges in the 3-ary \(n\)-cube
- Embedded paths and cycles in faulty hypercubes
- Hamiltonian paths and Hamiltonian cycles passing through prescribed linear forests in star graph with fault-tolerant edges
- Hamiltonian cycles passing through linear forests in k-ary n-cubes
- Hamiltonian laceability of hypercubes with prescribed linear forest and/or faulty edges
- From data completion to problems on hypercubes: a parameterized analysis of the independent set problem
- Matchings in hypercubes extend to long cycles
- From data completion to problems on hypercubes: a parameterized analysis of the independent set problem
- On prescribed Hamilton laceability of hybrid-faulty star graphs
- Matchings in hypercubes extend to long cycles
- Matchings with five directions in hypercubes extend to Hamilton cycles and paths with prescribed ends
- A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph
- Hamiltonian paths passing through linear forests in hypercubes with faulty edges
- Hybrid fault-tolerant prescribed hyper-Hamiltonian laceability of hypercubes
- On path bipancyclicity of hypercubes
- Hamiltonian paths and cycles passing through a prescribed path in hypercubes
This page was built for publication: Hamiltonian paths with prescribed edges in hypercubes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2370437)
