Hamiltonian paths with prescribed edges in hypercubes (Q2370437): Difference between revisions

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.