The minimum number of Hamilton cycles in a hamiltonian threshold graph of a prescribed order
classification
🧮 math.CO
keywords
graphminimumhamiltoniannumberorderthresholdcycleshamilton
read the original 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,\ldots,\lceil n/2\rceil,\lceil n/2\rceil,\ldots,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.$
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.