Splittance

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 G be any graph with n vertices, whose degrees in decreasing order are d₁ ≥ d₂ ≥ d₃ ≥ … ≥ d_n. Let m be the largest index for which d_i ≥ i – 1. Then the splittance of G is

${\displaystyle \sigma (G)={\tbinom {m}{2}}-{\frac {1}{2}}\sum _{i=1}^{m}d_{i}+{\frac {1}{2}}\sum _{i=m+1}^{n}d_{i}.}$

The given graph is a split graph already if σ(G) = 0. 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.^[2]