DEGREE SEQUENCES AND MAJORIZATION

A classical result concerning majorization is: given two nonnegative i nteger sequences a and b such that a majorizes b, a rearrangement of b can be obtained from a by a sequence of unit transformations. A recen t result says that a degree sequence is a threshold sequence (degree s equence of a threshold graph) if and only if it is not strictly majori zed by any degree sequence. Motivated by this, we define the majorizat ion gap of a degree sequence to be the minimum number of successive re verse unit transformations required to transform it into a threshold s equence. We derive a formula for the majorization gap by establishing a lower bound for it and exhibiting reverse unit transformations achie ving the bound. We also discuss the relationship between the majorizat ion gap and the threshold gap (introduced elsewhere), and show that th ey are equal. The degree sequences having the maximum majorization gap for a fixed number of edges or vertices are characterized.