This analysis explores Hamiltonian paths in hypercubes, revealing that matchings can support such paths.
The hypercube \( Q_n \) contains a Hamiltonian path joining \( x \) and \( y \) (where x and y from the opposite partite set) containing \( P \) if and only if the induced subgraph of \( P \) is a linear forest, where none of these paths have \( x \) or \( y \) as internal vertices nor both as endpoints. Dvořák and Gregor answered a problem posed by Caha and Koubek and proved that for every \( n ≥ 5 \), there exist vertices \( x \) and \( y \) with a set of \( 2n - 4 \) edges in \( Q_n \) that extend to the Hamiltonian path joining \( x \) and \( y \). This paper examines the Hamiltonian properties of hypercubes with a matching set. Let consider the hypercube \( Q_n \), for \( n ≥ 5 \) and a set of matching \( M \) such that \( |M| ≤ 3n - 13 \). We prove a Hamiltonian path exists joining two vertices x and y in \( Q_n \) from opposite partite sets containing M.
No takes yet. Share an insight, caveat, or question.
Ali et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: