Skip to content
DraconiticResearch
Search Sources API
201,683 studies31 sourcesUpdated 18 min ago
Peer-reviewedCC BY 4.0The Electronic Journal of Combinatorics

On the Minimum Number of Hamilton Cycles in Hamiltonian Threshold Graphs: A Simple Proof

  • Chengli Li
  • Feng Liu
Open at sourcePDFDOICite

Abstract

A graph is called a threshold graph if it is induced-{P4,C4,2K2} free. In 2020, Qiao and Zhan [J. Graph Theory 93 (2020) 222--229] determined the minimum number of Hamilton cycles in a Hamiltonian threshold graph and characterized the extremal graphs attaining this minimum. We show that every Hamiltonian threshold graph contains a special spanning subgraph, from which their two results follow directly.

Related

  1. Hamiltonian graphs with prescribed minimum degree and no near-spanning cycles
    Xingzhi Zhan
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. On the Number of Hamiltonian Cycles in a Boolean Cube
    A. L. Perezhogin, V. N. Potapov
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. The maximum number of Hamiltonian cycles in tournaments
    Alexander Divoux, Shouda Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. On Hamilton cycles in quasiprimitive graphs of order 2pq
    Hao Yu, Tianlei Zhou
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  5. Alternating Hamilton Paths and Cycles in Poset Products
    Yuxian Dong, Jianxi Mao
    arXivPreprintCC0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@article{li2026minimum,
  title = {{On the Minimum Number of Hamilton Cycles in Hamiltonian Threshold Graphs: A Simple Proof}},
  author = {Chengli Li and Feng Liu},
  journal = {The Electronic Journal of Combinatorics},
  year = {2026},
  month = oct,
  doi = {10.37236/15076},
  url = {https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p25},
  note = {CC BY 4.0},
}
RIS
TY  - JOUR
TI  - On the Minimum Number of Hamilton Cycles in Hamiltonian Threshold Graphs: A Simple Proof
AU  - Chengli Li
AU  - Feng Liu
PY  - 2026
DA  - 2026/10/23
JO  - The Electronic Journal of Combinatorics
DO  - 10.37236/15076
UR  - https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p25
AB  - A graph is called a threshold graph if it is induced-{P_4,C_4,2K_2} free. In 2020, Qiao and Zhan [J. Graph Theory 93 (2020) 222--229] determined the minimum number of Hamilton cycles in a Hamiltonian threshold graph and characterized the extremal graphs attaining this minimum. We show that every Hamiltonian threshold graph contains a special spanning subgraph, from which their two results follow directly.
SN  - 1077-8926
ER  -