Hamiltonian graphs with prescribed minimum degree and no near-spanning cycles
In 1984, Roland Häggkvist posed the problem of constructing Hamiltonian graphs of order $n$ with large minimum degree and no $(n-2)$-cycle. He remarked that he did not know of such a graph with minimum degree at least three. We solve this problem by proving the following two results. (1) For every integer $d\ge 3$ and every integer $n\ge 15d-14,$ there exists a Hamiltonian graph of order $n$ and minimum degree $d$ that contains no $(n-2)$-cycle. (2) For every integer $d\ge 3,$ every positive integer $k,$ and every integer $n\ge (k+1)[(d-1)(k+3)+1],$ there exists a Hamiltonian graph of order…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.05468
curl -X POST /api/v1/records/arxiv/2609.05468/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.05468/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'