Degree sequences and majorization (Q1322868)

The authors define the majorization gap of a degree sequence as the minimum number of successive reverse-unit-transformations required to transform it into a threshold sequence (i.e., the degree sequence of a threshold graph). They deduce a formula for the majorization gap (by establishing a lower bound for it and exhibiting reverse-unit- transformations achieving the bound). They also show that the majorization gap is equal to the so-called threshold gap and characterize the maximum majorization gap for a fixed number of edges or vertices. The contents of used notions must be consulted in the paper.