The hypercube <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$Q_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Q</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> is a fundamental structure in interconnection networks, where Hamiltonian paths and cycles play a key role in supporting efficient communication and routing. It is known that <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$Q_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Q</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> contains a Hamiltonian path between two vertices x and y from opposite partite sets that includes a prescribed set of edges. Dvořák and Gregor resolved a problem posed by Caha and Koubek by proving that for every <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$n \ge 5$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>5</mn> </mrow> </math></EquationSource> </InlineEquation>, there exist vertices x and y and a set of <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$2n - 4$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mi>n</mi> <mo>-</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation> edges in <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$Q_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Q</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> that can be extended to a Hamiltonian path between x and y. In this paper, we consider matchings M in <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$Q_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Q</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$n \ge 5$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>5</mn> </mrow> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$|M| \le 3n - 13$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">|</mo> <mi>M</mi> <mo stretchy="false">|</mo> <mo>≤</mo> <mn>3</mn> <mi>n</mi> <mo>-</mo> <mn>13</mn> </mrow> </math></EquationSource> </InlineEquation>. We show that for any two vertices x and y in opposite partite sets of <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$Q_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Q</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation>, there exists a Hamiltonian path between x and y that contains all edges of M.

Hamiltonian paths extending a set of matchings in hypercubes

期刊论文
发表日期：

2026年5月11日

查看全文

Abid Ali,
Lina Ba,
Weihua Yang

摘要

The hypercube $Q_n$ $Q_{n}$ is a fundamental structure in interconnection networks, where Hamiltonian paths and cycles play a key role in supporting efficient communication and routing. It is known that $Q_n$ $Q_{n}$ contains a Hamiltonian path between two vertices x and y from opposite partite sets that includes a prescribed set of edges. Dvořák and Gregor resolved a problem posed by Caha and Koubek by proving that for every $n \ge 5$ $n \geq 5$ , there exist vertices x and y and a set of $2n - 4$ $2 n - 4$ edges in $Q_n$ $Q_{n}$ that can be extended to a Hamiltonian path between x and y. In this paper, we consider matchings M in $Q_n$ $Q_{n}$ for $n \ge 5$ $n \geq 5$ with $|M| \le 3n - 13$ $| M | \leq 3 n - 13$ . We show that for any two vertices x and y in opposite partite sets of $Q_n$ $Q_{n}$ , there exists a Hamiltonian path between x and y that contains all edges of M.