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

:\sigma(G)=\tbinom{m}{2}-\frac12\sum_{i=1}^m d_i +\frac12\sum_{i=m+1}^n d_i.

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=

{{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

}}

{{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 }}

}}

Category:Graph invariants