graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a branch of mathematics, the splittance of an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

measures its distance from a

split graph In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by , and independently introduced by . A split graph may have m ...

. A split graph is a graph whose vertices can be partitioned into an independent set (with no edges within this subset) and a

clique A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popula ...

(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.

Calculation from degree sequence

The splittance of a graph can be calculated only from the

degree sequence In graph theory, the degree (or valency) of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex v is denoted ...

of the graph, without examining the detailed structure of the graph. Let be any graph with vertices, whose degrees in decreasing order are . Let be the largest index for which . Then the splittance of is :

\sigma(G)=\tbinom-\frac12\sum_^m d_i +\frac12\sum_^n d_i.

The given graph is a split graph already if . Otherwise, it can be made into a split graph by calculating , adding all missing edges between pairs of the 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 In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...

Applications

The splittance of a graph has been used in

parameterized complexity In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. ...

as a parameter to describe the efficiency of algorithms. For instance,

graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...

is fixed-parameter tractable under this parameter: it is possible to optimally color the graphs of bounded splittance in

References

{{reflist, refs= {{citation , last = Cai , first = Leizhen , doi = 10.1016/S0166-218X(02)00242-1 , issue = 3 , journal =

Discrete Applied Mathematics ''Discrete Applied Mathematics'' is a peer-reviewed scientific journal covering algorithmic and applied areas of discrete mathematics. It is published by Elsevier and the editor-in-chief is Endre Boros (Rutgers University). The journal was split o ...

, mr = 1976024 , pages = 415–429 , title = Parameterized complexity of vertex colouring , volume = 127 , year = 2003, doi-access = free {{citation , last1 = Hammer , first1 = Peter L. , author1-link = Peter L. Hammer , last2 = Simeone , first2 = Bruno , doi = 10.1007/BF02579333 , issue = 3 , journal =

Combinatorica ''Combinatorica'' is an international journal of mathematics, publishing papers in the fields of combinatorics and computer science. It started in 1981, with László Babai and László Lovász as the editors-in-chief with Paul Erdős as hono ...

, mr = 637832 , pages = 275–284 , title = The splittance of a graph , volume = 1 , year = 1981 Graph invariants