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

Abstract

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.