Threshold Graph

A threshold graph is a nonempty finite simple graph that can be constructed from a single graph vertex by repeatedly adjoining either an isolated vertex or a new graph vertex adjacent to all existing vertices (Mahadev and Peled 1995). Equivalently, nonnegative weights and a threshold can be assigned so that two distinct vertices are adjacent iff .

A nonempty finite simple graph is a threshold graph iff it has no vertex-induced subgraph isomorphic to , , or , where is a path graph, is a cycle graph, and consists of two disjoint graph edges. Every threshold graph is a split graph, and its degree sequence determines it uniquely up to graph isomorphism (Mahadev and Peled 1995; Li and Liu 2026, p. 2).

For , define on by joining distinct iff . This is the Hamiltonian threshold graph whose degree sequence is , with . Here is the ceiling function. Every Hamiltonian threshold graph on vertices contains as a spanning subgraph (Li and Liu 2026, p. 4).

The minimum number of Hamiltonian cycles in a Hamiltonian threshold graph on vertices is

where is the floor function. Equality holds uniquely up to graph isomorphism for (Qiao and Zhan 2020; Li and Liu 2026, pp. 3-4).