<p>Fault tolerance is important to consider because link or node faults can occur in networks. In this study, we investigate the Hamiltonian properties of hypercubes under certain conditions on faulty edges. Let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$Q_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Q</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> be an <i>n</i>-dimensional hypercube with <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$ n \ge 5 $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>5</mn> </mrow> </math></EquationSource> </InlineEquation> and let <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$ F $</EquationSource> <EquationSource Format="MATHML"><math> <mi>F</mi> </math></EquationSource> </InlineEquation> be a set of faulty edges satisfying <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$ |F| \le 4n - 18 $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">|</mo> <mi>F</mi> <mo stretchy="false">|</mo> <mo>≤</mo> <mn>4</mn> <mi>n</mi> <mo>-</mo> <mn>18</mn> </mrow> </math></EquationSource> </InlineEquation>. We prove that a Hamiltonian path exists in <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$ Q_n - F $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>Q</mi> <mi>n</mi> </msub> <mo>-</mo> <mi>F</mi> </mrow> </math></EquationSource> </InlineEquation> connecting any two vertices from distinct partite sets if they satisfy the following two conditions: (i) every vertex has degree at least 2, and (ii) at most one vertex has degree 2. These findings provide insights into the fault tolerance of hypercube networks.</p>

Hamiltonian laceability with a set of faulty edges in hypercubes

期刊论文
发表日期：

2026年4月30日

查看全文

Abid Ali,
Weihua Yang

摘要

Fault tolerance is important to consider because link or node faults can occur in networks. In this study, we investigate the Hamiltonian properties of hypercubes under certain conditions on faulty edges. Let $Q_n$ $Q_{n}$ be an n-dimensional hypercube with $ n \ge 5 $ $n \geq 5$ and let $ F $ $F$ be a set of faulty edges satisfying $ |F| \le 4n - 18 $ $| F | \leq 4 n - 18$ . We prove that a Hamiltonian path exists in $ Q_n - F $ $Q_{n} - F$ connecting any two vertices from distinct partite sets if they satisfy the following two conditions: (i) every vertex has degree at least 2, and (ii) at most one vertex has degree 2. These findings provide insights into the fault tolerance of hypercube networks.