splittance
{{Short description|Distance of a graph from a split graph}}
File:Splittance.svg, 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.{{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
:
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
{{reflist|refs=
| 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
}}
| 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 }}
}}