{{Short description|Distance of a graph from a split graph}} [[File:Splittance.svg|thumb|upright=1.2|Two graphs with '''splittance''' 0 and 2, respectively. The first is therefore a split graph, and the second would need the solid red edge removed and the dashed red edge added to become 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.{{r|hamsim}}
==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 {{mvar|G}} be any graph with {{mvar|n}} vertices, whose degrees in decreasing order are {{math|''d''{{sub|1}} ≥ ''d''{{sub|2}} ≥ ''d''{{sub|3}} ≥ … ≥ ''d{{sub|n}}''}}. Let {{mvar|m}} be the largest index for which {{math|''d{{sub|i}}'' ≥ ''i'' – 1}}. Then the splittance of {{mvar|G}} is :<math>\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 {{math|1=''σ''(''G'') = 0}}. Otherwise, it can be made into a split graph by calculating {{mvar|m}}, adding all missing edges between pairs of the {{mvar|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.{{r|hamsim}}
==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.{{r|cai}}
==References== <references>
<ref name=cai>{{citation | last = Cai | first = Leizhen | doi = 10.1016/S0166-218X(02)00242-1 | issue = 3 | journal = Discrete Applied Mathematics | mr = 1976024 | pages = 415–429 | title = Parameterized complexity of vertex colouring | volume = 127 | year = 2003| doi-access = free | citeseerx = 10.1.1.104.3789 }}</ref>
<ref name=hamsim>{{citation | last1 = Hammer | first1 = Peter L. | author1-link = Peter L. Hammer | last2 = Simeone | first2 = Bruno | doi = 10.1007/BF02579333 | issue = 3 | journal = Combinatorica | mr = 637832 | pages = 275–284 | title = The splittance of a graph | volume = 1 | year = 1981| s2cid = 30335319 }}</ref>
</references>
Category:Graph invariants