Delphi.science

On the Complexity of Extending Prescribed Linear Forests to Hamiltonian Cycles in Hypercubes

Source: arxiv.org/abs/2611.11476

Huazhong Lü, Tingzeng Wu

arXivarxiv/2611.11476Nov 8, 2026cs.CCscore 0

Let $Q_n$ be the $n$-dimensional hypercube, and let $P\subseteq E(Q_n)$ be a set of prescribed edges. It is known that, for $n\ge 2$, every such set $P$ with $|P|\leq 2n-3$ whose edges form a linear forest is contained in a Hamiltonian cycle of $Q_n$. This bound is sharp for general linear forests. The computational complexity of deciding whether a prescribed edge set of a hypercube can be extended to a Hamiltonian cycle was posed as an open question by Dvořák [SIAM J. Discrete Math. 19 (2005) 135--144]. We prove that the problem is NP-complete even when the prescribed edges form a spanning…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.11476
curl -X POST /api/v1/records/arxiv/2611.11476/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.11476/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'