# Splittance

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Splittance
> Markdown URL: https://mediated.wiki/source/Splittance.md
> Source: https://en.wikipedia.org/wiki/Splittance
> Source revision: 1337341802
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{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](/source/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](/source/graph_theory), a branch of mathematics, the '''splittance''' of an [undirected graph](/source/undirected_graph) measures its distance from a [split graph](/source/split_graph). A split graph is a graph whose vertices can be partitioned into an [independent set](/source/independent_set_(graph_theory)) (with no edges within this subset) and a [clique](/source/clique_(graph_theory)) (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](/source/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](/source/linear_time).{{r|hamsim}}

==Applications==
The splittance of a graph has been used in [parameterized complexity](/source/parameterized_complexity) as a parameter to describe the efficiency of algorithms. For instance, [graph coloring](/source/graph_coloring) is fixed-parameter tractable under this parameter: it is possible to optimally color the graphs of bounded splittance in [linear time](/source/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](/source/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](/source/Combinatorica)
 | mr = 637832
 | pages = 275–284
 | title = The splittance of a graph
 | volume = 1
 | year = 1981| s2cid = 30335319 }}</ref>

</references>

Category:Graph invariants

---
Adapted from the Wikipedia article [Splittance](https://en.wikipedia.org/wiki/Splittance) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Splittance?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.