Hamiltonian threshold graphs

The vertices of a threshold graph G are partitioned into a clique K and an independent set I so that the neighborhoods of the vertices of I are totally ordered by inclusion. The question of whether G is hamiltonian is reduced to the case that K and I have the same size, say r, in which case the edges of K do not affect the answer and may be dropped from G, yielding a bipartite graph B. Let d₁≤d₂≤…≤d_r and e₁≤e₂≤…≤e_r be the degrees in B of the vertices of I and K, respectively. For each q = 0, 1,…,r−1, denote by S_q the following system of inequalities: d_j⩾j + 1, j = 1,2,…,q, e_j⩾j + 1, j = 1, 2,…, r−1−1. Then the following conditions are equivalent:

• 1.(1) B is hamiltonian,
• 2.(2) S_q holds for some q = 0, 1,…, r−1,
• 3.(3) S_q holds for each q = 0, 1,…, r−1.