Splittance

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.

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 (with no edges within this subset) and a clique (having all possible edges within this subset). The splittance is the smallest number of edge additions and removals that transform the given graph into a split graph.Template:R

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 Template:Mvar be any graph with Template:Mvar vertices, whose degrees in decreasing order are Template:Math. Let Template:Mvar be the largest index for which Template:Math. Then the splittance of Template:Mvar is

$\sigma (G)=(\genfrac{}{}{0ex}{}{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 Template:Math. Otherwise, it can be made into a split graph by calculating Template:Mvar, adding all missing edges between pairs of the Template:Mvar 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.Template:R

Applications

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.Template:R