Hamiltonian paths extending a set of matchings in hypercubes
Hamiltonian paths extending a set of matchings in hypercubes
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 \geq 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 \geq 5 \) and a set of matching \( M \) such that \( |M| \leq 3n - 13 \). We prove a Hamiltonian path exists joining two vertices $x$ and $y$ in \( Q_n \) from opposite partite sets containing $M$.
Abid Ali、Lina Ba、Weihua Yang
数学
Abid Ali,Lina Ba,Weihua Yang.Hamiltonian paths extending a set of matchings in hypercubes[EB/OL].(2025-06-26)[2025-07-16].https://arxiv.org/abs/2506.21432.点此复制
评论