Threshold Sequences
P. L. Hammer, Toshihide Ibaraki, Bruno Simeone · SIAM Journal on Algebraic and Discrete Methods · 1981
A graph is threshold if there is a hyperplane separating the characteristic vectors of the independent sets from the characteristic vectors of the nonindependent sets. A sequence of n nonnegative integers is a threshold sequence if it is the degree sequence of a threshold graph with n vertices. Several characterizations of threshold sequences are given, and it is shown that the set of threshold sequences forms a lattice. For an arbitrary degree sequence d (not necessarily threshold), the minimum distance between d and a threshold sequence is called the threshold gap. Its properties are discussed, and the set of threshold sequences at minimum distance from d is also characterized.