Splittance
In graph theory, a branch of mathematics, the splittance of an undirected graph measures its distance from a split graph. A split graph is a graph whose vertices can be partitioned into an independent set and a clique. The splittance is the smallest number of edge additions and removals that transform the given graph into a split graph.
Calculation from degree sequence
The splittance of a graph can be calculated only from the degree sequence of the graph, without examining the detailed structure of the graph. Let be any graph with vertices, whose degrees in decreasing order are. Let be the largest index for which. Then the splittance of isThe given graph is a split graph already if. Otherwise, it can be made into a split graph by calculating, adding all missing edges between pairs of the vertices of maximum degree, and removing all edges between pairs of the remaining vertices. As a consequence, the splittance and a sequence of edge additions and removals that realize it can be computed in linear time.