The minimum number of Hamilton cycles in a hamiltonian threshold graph of a prescribed order

2018/02/26 by Pu Qiao, Qiao, Pu, Xingzhi Zhan +1
Computer Science · Mathematics · #05C35 #05C45 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1802.09250

openalex publication_date 2018/02/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that the minimum number of Hamilton cycles in a hamiltonian threshold graph of order n is 2^{\lfloor (n-3)/2\rfloor} and this minimum number is attained uniquely by the graph with degree sequence n-1,n-1,n-2,…,\lceil n/2\rceil,\lceil n/2\rceil,…,3,2 of n-2 distinct degrees. This graph is also the unique graph of minimum size among all hamiltonian threshold graphs of order n.

Related

• Notes on Hamiltonian threshold and chain graphs
• A Size Bound for Hamilton Cycles
• On the Number of Cycles in a Graph
• On the Minimum Number of Hamiltonian Cycles in Regular Graphs
• Graphs with Many Hamiltonian Paths