PreprintarXiv licencearXiv
Degree sequence condition for pancyclicity in tough graphs
Abstract
Let t ≥ 1 be an integer, and let G be a t-tough n-vertex graph with degree sequence d1, d2, …, dn in non-decreasing order. In 1995, Hoàng conjectured that if G is Hamiltonian and, for every integer i satisfying t≤ i<n/2, di≤ i, and dn−i+t<n−i, one has dj + dn−j+t ≥ n for all j with i < j < n/2, then G is pancyclic or bipartite. In this paper, we disprove the conjecture for t = 1 and confirm it for all t ≥ 7.
Related
- On the maximally edge-connected square graphs with degree sequence conditions
- A Bang-Jensen-Gutin-Li type condition for pancyclicity in digraphs
- Graphs versus loopless digraphs with a given degree sequence, and convergence of uniformly random graphs at every density
- P-stable degree sequence regions for bipartite and directed graphs
- Polynomial Length Cycles In Tough Graphs
BibTeX
@misc{shan2026degree,
title = {{Degree sequence condition for pancyclicity in tough graphs}},
author = {Songling Shan and Zachary Warren},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23107},
eprint = {2609.23107},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23107},
}
RIS
TY - UNPB
TI - Degree sequence condition for pancyclicity in tough graphs
AU - Songling Shan
AU - Zachary Warren
PY - 2026
DA - 2026/09/19
PB - arXiv
DO - 10.48550/arxiv.2609.23107
UR - https://arxiv.org/abs/2609.23107
AB - Let t ≥ 1 be an integer, and let G be a t-tough n-vertex graph with degree sequence d_1, d_2, …, d_n in non-decreasing order. In 1995, Hoàng conjectured that if G is Hamiltonian and, for every integer i satisfying t≤ i<n/2, d_i≤ i, and d_n−i+t<n−i, one has d_j + d_n−j+t ≥ n for all j with i < j < n/2, then G is pancyclic or bipartite. In this paper, we disprove the conjecture for t = 1 and confirm it for all t ≥ 7.
ER -