Splittance Explained

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.

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 is

\sigma(G) = \tbinom{m}{ 2 } - (12 \sum)/(_{i=1}) ^{m} d _{i} + (12 \sum)/(_{i=m+1}) ^{n} d _{i.} The 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.

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.