{"id":"arxiv/2609.05468","url":"https://arxiv.org/abs/2609.05468","tags":["math.CO"],"score":0,"title":"Hamiltonian graphs with prescribed minimum degree and no near-spanning cycles","domain":"math.CO","source":"arxiv","authors":["Xingzhi Zhan"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-20","reactions":{}}