Splittance

Let G be any graph with n vertices, whose degrees in decreasing order are d1 ≥ d2 ≥ d3 ≥ … ≥ dn.

Otherwise, it can be made into a split graph by calculating m, adding all missing edges between pairs of the m 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.

[1] The splittance of a graph has been used in parameterized complexity as a parameter to describe the efficiency of algorithms.

For instance, graph coloring is fixed-parameter tractable under this parameter: it is possible to optimally color the graphs of bounded splittance in linear time.

Left: A split graph , with a clique in blue and an independent set in red. Right: A graph with splittance 2, because if one edge was added (dotted line between vertices 2 and 3) and one was removed (line with an "X" between 7 and 8), it would be a split graph.