pith. sign in

arxiv: 1802.09250 · v1 · pith:R7U4NYMYnew · submitted 2018-02-26 · 🧮 math.CO

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

classification 🧮 math.CO
keywords graphminimumhamiltoniannumberorderthresholdcycleshamilton
0
0 comments X
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.