Hamiltonian threshold graphs (Q1080870): Difference between revisions

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_ 1\leq d_ 2\leq...\leq d_ r\) and \(e_ 1\leq e_ 2\leq...\leq 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: a) \(d_ j\geq j+1\), \(j=1,2,...,q\), and b) \(e_ j\geq j+1\), \(j=1,2,...,r- q-1.\) Then the following conditions are equivalent: (1) B is hamiltonian, (2) \(S_ q\) holds for some \(q=0,1,...,r-1\), (3) \(S_ q\) holds for each \(q=0,1,...,r-1\).