PreprintarXiv licencearXiv
Hamiltonian graphs with prescribed minimum degree and no near-spanning cycles
Abstract
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≥ 3 and every integer n≥ 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≥ 3, every positive integer k, and every integer n≥ (k+1)[(d−1)(k+3)+1], there exists a Hamiltonian graph of order n and minimum degree d that contains no (n−s)-cycle for any s∈{1,2,…,k}. The proofs are constructive. We also pose several open problems.
Related
- Spanning Trees with Many Leaves in Graphs of Minimum Degree at Least 7
- Degree sequences of spectrally extremal connected nonregular graphs with prescribed maximum degree: the dense case
- Total-coloring of planar graphs with maximum degree 6 and without prescribed 4-cycles
- On the Minimum Number of Hamilton Cycles in Hamiltonian Threshold Graphs: A Simple Proof
- Unbalanced spectral Turán problem for color-critical graphs with prescribed large maximum degree
BibTeX
@misc{zhan2026hamiltonian,
title = {{Hamiltonian graphs with prescribed minimum degree and no near-spanning cycles}},
author = {Xingzhi Zhan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05468},
eprint = {2609.05468},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05468},
}
RIS
TY - UNPB
TI - Hamiltonian graphs with prescribed minimum degree and no near-spanning cycles
AU - Xingzhi Zhan
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.05468
UR - https://arxiv.org/abs/2609.05468
AB - 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≥ 3 and every integer n≥ 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≥ 3, every positive integer k, and every integer n≥ (k+1)[(d−1)(k+3)+1], there exists a Hamiltonian graph of order n and minimum degree d that contains no (n−s)-cycle for any s∈{1,2,…,k}. The proofs are constructive. We also pose several open problems.
ER -