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 (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.[1]
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 G be any graph with n vertices, whose degrees in decreasing order are d1 ≥ d2 ≥ d3 ≥ … ≥ dn. Let m be the largest index for which di ≥ i – 1. Then the splittance of G is
- [math]\displaystyle{ \sigma(G)=\tbinom{m}{2}-\frac12\sum_{i=1}^m d_i +\frac12\sum_{i=m+1}^n d_i. }[/math]
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]
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.[2]
References
- ↑ 1.0 1.1 "The splittance of a graph", Combinatorica 1 (3): 275–284, 1981, doi:10.1007/BF02579333
- ↑ Cai, Leizhen (2003), "Parameterized complexity of vertex colouring", Discrete Applied Mathematics 127 (3): 415–429, doi:10.1016/S0166-218X(02)00242-1
 |  |
