# Split graph

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

{{short description|Graph which partitions into a clique and independent set}}
{{about|graphs that can be partitioned into a clique and an independent set|cuts that form complete bipartite graphs|split (graph theory)}}
thumb|240px|A split graph, partitioned into a clique and an independent set.

In [graph theory](/source/graph_theory), a branch of mathematics, a '''split graph''' is a [graph](/source/Graph_(discrete_mathematics)) in which the [vertices](/source/Vertex_(graph_theory)) can be [partitioned](/source/Graph_partition) into a [clique](/source/clique_(graph_theory)) and an [independent set](/source/Independent_set_(graph_theory)). Split graphs were first studied by {{harvs|last1=Földes|author2-link=Peter Ladislaw Hammer|last2=Hammer|year=1977a|year2=1977b|txt}}, and independently introduced by {{harvs|author1-link=Regina Tyshkevich|last1=Tyshkevich|last2=Chernyak|year=1979|txt}}, where they called these graphs "polar graphs" ({{langx|ru|полярные графы}}).<ref>{{harvtxt|Földes|Hammer|1977a}} had a more general definition, in which the graphs they called split graphs also included [bipartite graph](/source/bipartite_graph)s (that is, graphs that be partitioned into two independent sets) and the [complements](/source/complement_(graph_theory)) of bipartite graphs (that is, graphs that can be partitioned into two cliques). {{harvtxt|Földes|Hammer|1977b}} use the definition given here, which has been followed in the subsequent literature; for instance, it is {{harvtxt|Brandstädt|Le|Spinrad|1999}}, Definition 3.2.3, p.41.</ref>

A split graph may have more than one partition into a clique and an independent set; for instance, the [path](/source/Path_graph) {{math|''a''–''b''–''c''}} is a split graph, the vertices of which can be partitioned in three different ways:
#the clique {{math|{''a'', ''b''} }} and the independent set {{math|{''c''} }}
#the clique {{math|{''b'', ''c''} }} and the independent set {{math|{''a''} }}
#the clique {{math|{''b''} }} and the independent set {{math|{''a'', ''c''} }}

Split graphs can be characterized in terms of their [forbidden induced subgraph](/source/forbidden_induced_subgraph)s: a graph is split if and only if no [induced subgraph](/source/induced_subgraph) is a [cycle](/source/cycle_graph) on four or five vertices, or a pair of disjoint edges (the complement of a 4-cycle).<ref>{{harvtxt|Földes|Hammer|1977a}}; {{harvtxt|Golumbic|1980}}, Theorem 6.3, p. 151.</ref>

==Relation to other graph families==
From the definition, split graphs are clearly closed under [complementation](/source/complement_(graph_theory)).<ref>{{harvtxt|Golumbic|1980}}, Theorem 6.1, p. 150.</ref> Another characterization of split graphs involves complementation: they are [chordal graph](/source/chordal_graph)s the [complements](/source/complement_(graph_theory)) of which are also chordal.<ref>{{harvtxt|Földes|Hammer|1977a}}; {{harvtxt|Golumbic|1980}}, Theorem 6.3, p. 151; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, Theorem 3.2.3, p. 41.</ref> Just as chordal graphs are the [intersection graph](/source/intersection_graph)s of subtrees of trees, split graphs are the intersection graphs of distinct substars of [star graph](/source/star_graph)s.<ref>{{harvtxt|McMorris|Shier|1983}}; {{harvtxt|Voss|1985}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, Theorem 4.4.2, p. 52.</ref> [Almost all](/source/Almost_all) chordal graphs are split graphs; that is, in the limit as ''n'' goes to infinity, the fraction of ''n''-vertex chordal graphs that are split approaches one.<ref>{{harvtxt|Bender|Richmond|Wormald|1985}}.</ref>

Because chordal graphs are [perfect](/source/perfect_graph), so are the split graphs. The '''double split graphs''', a family of graphs derived from split graphs by doubling every vertex (so the clique comes to induce an antimatching and the independent set comes to induce a matching), figure prominently as one of five basic classes of perfect graphs from which all others can be formed in the proof by {{harvtxt|Chudnovsky|Robertson|Seymour|Thomas|2006}} of the [Strong Perfect Graph Theorem](/source/Strong_Perfect_Graph_Theorem).

If a graph is both a split graph and an [interval graph](/source/interval_graph), then its complement is both a split graph and a [comparability graph](/source/comparability_graph), and vice versa. The split comparability graphs, and therefore also the split interval graphs, can be characterized in terms of a set of three forbidden induced subgraphs.<ref>{{harvtxt|Földes|Hammer|1977b}}; {{harvtxt|Golumbic|1980}}, Theorem 9.7, page 212.</ref> The split [cograph](/source/cograph)s are exactly the [threshold graph](/source/threshold_graph)s. The split [permutation graph](/source/permutation_graph)s are exactly the interval graphs that have interval graph complements;<ref>{{harvtxt|Brandstädt|Le|Spinrad|1999}}, Corollary 7.1.1, p. 106, and Theorem 7.1.2, p. 107.</ref>
these are the permutation graphs of [skew-merged permutation](/source/skew-merged_permutation)s.{{sfnp|Kézdy|Snevily|Wang|1996}} Split graphs have [cochromatic number](/source/cocoloring) 2.

==Algorithmic problems==
Let {{mvar|G}} be a split graph, partitioned into a clique {{mvar|C}} and an independent set {{mvar|i}}. Then every [maximal clique](/source/maximal_clique) in a split graph is either {{mvar|C}} itself, or the [neighborhood](/source/neighborhood_(graph_theory)) of a vertex in {{mvar|i}}. Thus, it is easy to identify the maximum clique, and complementarily the [maximum independent set](/source/maximum_independent_set) in a split graph. In any split graph, one of the following three possibilities must be true:<ref>{{harvtxt|Hammer|Simeone|1981}}; {{harvtxt|Golumbic|1980}}, Theorem 6.2, p. 150.</ref>
# There exists a vertex {{mvar|x}} in {{mvar|i}} such that {{math|''C'' ∪ {''x''} }} is complete. In this case,  {{math|''C'' ∪ {''x''} }} is a maximum clique and {{mvar|i}} is a maximum independent set.
# There exists a vertex {{mvar|x}} in {{mvar|C}} such that {{math|''i'' ∪ {''x''} }} is independent. In this case,  {{math|''i'' ∪ {''x''} }} is a maximum independent set and {{mvar|C}} is a maximum clique.
# {{mvar|C}} is a maximal clique and {{mvar|i}} is a maximal independent set. In this case, {{mvar|G}} has a unique partition {{math|(''C'', ''i'')}} into a clique and an independent set, {{mvar|C}} is the maximum clique, and {{mvar|i}} is the maximum independent set.

Some other optimization problems that are [NP-complete](/source/NP-complete) on more general graph families, including [graph coloring](/source/graph_coloring), are similarly straightforward on split graphs. Finding a [Hamiltonian cycle](/source/Hamiltonian_cycle) remains [NP-complete](/source/NP-complete) even for split graphs which are [strongly chordal graph](/source/strongly_chordal_graph)s.<ref>{{harvtxt|Müller|1996}}</ref> It is also well known that the Minimum Dominating Set problem remains [NP-complete](/source/NP-complete) for split graphs.<ref>{{harvtxt|Bertossi|1984}}</ref>

==Degree sequences==
One remarkable property of split graphs is that they can be recognized solely from their [degree sequence](/source/degree_sequence)s. Let the degree sequence of a graph {{mvar|G}} be {{math|''d''{{sub|1}} ≥ ''d''{{sub|2}} ≥ … ≥ ''d{{sub|n}}''}}, and let {{mvar|m}} be the largest value of {{mvar|i}} such that {{math|''d{{sub|i}}'' ≥ ''i'' – 1}}. Then {{mvar|G}} is a split graph if and only if
:<math>\sum_{i=1}^m d_i = m(m-1) + \sum_{i=m+1}^n d_i.</math>
If this is the case, then the {{mvar|m}} vertices with the largest degrees form a maximum clique in {{mvar|G}}, and the remaining vertices constitute an independent set.<ref>{{harvtxt|Hammer|Simeone|1981}}; {{harvtxt|Tyshkevich|1980}}; {{harvtxt|Tyshkevich|Melnikow|Kotov|1981}}; {{harvtxt|Golumbic|1980}}, Theorem 6.7 and Corollary 6.8, p. 154; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, Theorem 13.3.2, p. 203. {{harvtxt|Merris|2003}} further investigates the degree sequences of split graphs.</ref>

The [splittance](/source/splittance) of an arbitrary graph measures the extent to which this inequality fails to be true. If a graph is not a split graph, then the smallest sequence of edge insertions and removals that make it into a split graph can be obtained by adding all missing edges between the {{mvar|m}} vertices with the largest degrees, and removing all edges between pairs of the remaining vertices; the splittance counts the number of operations in this sequence.{{sfnp|Hammer|Simeone|1981}}

==Counting split graphs==
{{harvtxt|Royle|2000}} showed that ([unlabeled](/source/Graph_labeling)) ''n''-vertex split graphs are in [one-to-one correspondence](/source/one-to-one_correspondence) with certain [Sperner families](/source/Sperner_families). Using this fact, he  determined a formula for the number of [nonisomorphic](/source/graph_isomorphism) split graphs on ''n'' vertices. For small values of ''n'', starting from ''n'' = 1, these numbers are
:1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... {{OEIS|id = A048194}}.
This [enumerative](/source/graph_enumeration) result was also proved earlier by {{harvtxt|Tyshkevich|Chernyak|1990}}.

==Notes==
{{reflist|30em}}

==References==
{{refbegin|30em}}
*{{citation
 | last1 = Bender | first1 = E. A.
 | last2 = Richmond | first2 = L. B.
 | last3 = Wormald | first3 = N. C.
 | title = Almost all chordal graphs split
 | journal = J. Austral. Math. Soc.
 | volume = 38
 | year = 1985
 | issue = 2
 | mr = 0770128
 | pages = 214–221
 | doi = 10.1017/S1446788700023077| doi-access = free
 }}.
*{{citation
 | last = Bertossi | first = Alan A.
 | title = Dominating sets for split and bipartite graphs
 | journal = [Information Processing Letters](/source/Information_Processing_Letters)
 | volume = 19
 | year = 1984
 | pages = 37–40
 | doi=10.1016/0020-0190(84)90126-1
}}.
*{{citation
 | last1 = Brandstädt
 | first1 = Andreas
 | author1-link = Andreas Brandstädt
 | last2 = Le
 | first2 = Van Bang
 | last3 = Spinrad
 | first3 = Jeremy
 | title = Graph Classes: A Survey
 | publisher = SIAM Monographs on Discrete Mathematics and Applications
 | year = 1999
 | isbn = 0-89871-432-X
 | url-access = registration
 | url = https://archive.org/details/graphclassessurv0000bran
 }}.
*{{citation
 | last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky
 | last2 = Robertson | first2 = Neil | author2-link = Neil Robertson (mathematician)
 | last3 = Seymour | first3 = Paul | author3-link = Paul Seymour (mathematician)
 | last4 = Thomas | first4 = Robin | author4-link = Robin Thomas (mathematician)
 | title = The strong perfect graph theorem
 | journal = [Annals of Mathematics](/source/Annals_of_Mathematics)
 | volume = 164
 | year = 2006
 | issue = 1
 | pages = 51–229
 | mr = 2233847
 | doi = 10.4007/annals.2006.164.51| arxiv = math/0212070}}.
*{{citation
 | last1 = Földes | first1 = Stéphane
 | last2 = Hammer | first2 = Peter Ladislaw | author2-link =Peter Ladislaw Hammer
 | contribution = Split graphs
 | title = Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977)
 | pages = 311–315
 | series = Congressus Numerantium
 | volume = XIX
 | publisher = Utilitas Math.
 | location = Winnipeg
 | year = 1977a
 | mr = 0505860}}.
*{{citation
 | last1 = Földes | first1 = Stéphane
 | last2 = Hammer | first2 = Peter Ladislaw | author2-link =Peter Ladislaw Hammer
 | title = Split graphs having Dilworth number two
 | journal = [Canadian Journal of Mathematics](/source/Canadian_Journal_of_Mathematics)
 | volume = 29
 | year = 1977b
 | issue = 3
 | pages = 666–672
 | mr = 0463041
 | doi = 10.4153/CJM-1977-069-1| doi-access = free
 }}.
*{{citation
 | last = Golumbic | first = Martin Charles | authorlink = Martin Charles Golumbic
 | title = Algorithmic Graph Theory and Perfect Graphs
 | publisher = Academic Press
 | year = 1980
 | isbn = 0-12-289260-7
 | mr = 0562306}}.
*{{citation
 | last1 = Hammer | first1 = Peter Ladislaw | author1-link = Peter Ladislaw Hammer
 | last2 = Simeone | first2 = Bruno
 | title = The splittance of a graph
 | journal = [Combinatorica](/source/Combinatorica)
 | volume = 1
 | year = 1981
 | issue = 3
 | pages = 275–284
 | mr = 0637832
 | doi = 10.1007/BF02579333}}.
*{{citation
 | last1 = Kézdy | first1 = André E.
 | last2 = Snevily | first2 = Hunter S.
 | last3 = Wang | first3 = Chi
 | doi = 10.1016/S0097-3165(96)80012-4
 | issue = 2
 | journal = Journal of Combinatorial Theory, Series A
 | mr = 1370138
 | pages = 353–359
 | title = Partitioning permutations into increasing and decreasing subsequences
 | volume = 73
 | year = 1996| doi-access = free
 }}.
*{{citation
 | last1 = McMorris | first1 = F. R.
 | last2 = Shier | first2 = D. R.
 | title = Representing chordal graphs on ''K''<sub>1,''n''</sub>
 | journal = Commentationes Mathematicae Universitatis Carolinae
 | volume = 24
 | year = 1983
 | pages = 489–494
 | mr = 0730144}}.
*{{citation
 | last = Merris | first = Russell
 | title = Split graphs
 | journal = [European Journal of Combinatorics](/source/European_Journal_of_Combinatorics)
 | volume = 24
 | year = 2003
 | issue = 4
 | pages = 413–430
 | doi = 10.1016/S0195-6698(03)00030-1
 | mr = 1975945| doi-access = free
 }}.
*{{citation
 | last = Müller | first = Haiko
 | title = Hamiltonian Circuits in Chordal Bipartite Graphs
 | journal = [Discrete Mathematics](/source/Discrete_Mathematics_(journal))
 | volume = 156
 | year = 1996
 | issue = 1–3
 | pages = 291–298
 | doi=10.1016/0012-365x(95)00057-4
| doi-access = free
 }}.
*{{citation
 | last = Royle | first = Gordon F. | authorlink = Gordon Royle
 | title = Counting set covers and split graphs
 | journal = Journal of Integer Sequences
 | volume = 3
 | year = 2000
 | issue = 2
 | pages = 00.2.6
 | mr = 1778996
 | url = http://www.emis.de/journals/JIS/VOL3/ROYLE/royle.pdf}}.
*{{Citation
 | last = Tyshkevich | first = Regina I. | authorlink=Regina Tyshkevich
 | title = [The canonical decomposition of a graph]
 | language = Russian
 | journal = [Doklady Akademii Nauk SSSR](/source/Doklady_Akademii_Nauk_SSSR)
 | volume = 24
 | year = 1980
 | pages = 677–679
 | mr = 0587712}}
*{{citation
 | last1 = Tyshkevich | first1 = Regina I. | author1-link=Regina Tyshkevich
 | last2 = Chernyak | first2 = A. A.
|script-title=ru:Каноническое разложение графа, определяемого степенями его вершин
 | title = Canonical partition of a graph defined by the degrees of its vertices
| url = https://elib.bspu.by/bitstream/doc/52431/1/%d0%9a%d0%90%d0%9d%d0%9e%d0%9d%d0%98%d0%a7%d0%95%d0%a1%d0%9a%d0%9e%d0%95%20%d0%a0%d0%90%d0%97%d0%9b%d0%9e%d0%96%d0%95%d0%9d%d0%98%d0%95%20%d0%93%d0%a0%d0%90%d0%a4%d0%90%2c%20%d0%9e%d0%9f%d0%a0%d0%95%d0%94%d0%95%d0%9b%d0%af%d0%95%d0%9c%d0%9e%d0%93%d0%9e%20%d0%a1%d0%a2%d0%95%d0%9f%d0%95%d0%9d%d0%af%d0%9c%d0%98%20%d0%95%d0%93%d0%9e%20%d0%92%d0%95%d0%a0%d0%a8%d0%98%d0%9d.pdf
 | language = Russian
 | year = 1979
 | journal = Isv. Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk
 | volume = 5
 | pages = 14–26
 | mr = 0554162}}.
*{{citation
 | last1 = Tyshkevich | first1 = Regina I. | author1-link=Regina Tyshkevich
 | last2 = Chernyak | first2 = A. A.
 | script-title=ru:Еще один метод перечисления непомеченных комбинаторных объектов
 | language = Russian
 | year = 1990
 | journal = Mat. Zametki
 | volume = 48
 | pages = 98–105
 | mr = 1102626
 | url = http://mi.mathnet.ru/eng/mz3413
 | issue = 6}}. Translated as "Yet another method of enumerating unmarked combinatorial objects" (1990), ''Mathematical notes of the Academy of Sciences of the USSR'' '''48''' (6): 1239–1245, {{doi|10.1007/BF01240267}}.
*{{citation
 | last1 = Tyshkevich | first1 = Regina I. | author1-link=Regina Tyshkevich
 | last2 = Melnikow | first2 = O. I.
 | last3 = Kotov | first3 = V. M.
 | title = On graphs and degree sequences: the canonical decomposition
 | language = Russian
 | journal = Kibernetika
 | volume = 6
 | year = 1981
 | pages = 5–8
 | mr = 0689420}}.
*{{citation
 | last = Voss | first = H.-J.
 | title = Note on a paper of McMorris and Shier
 | journal = Commentationes Mathematicae Universitatis Carolinae
 | volume = 26
 | year = 1985
 | pages = 319–322
 | mr = 0803929}}.
{{refend}}

==Further reading==
*A chapter on split graphs appears in the book by [Martin Charles Golumbic](/source/Martin_Charles_Golumbic), "Algorithmic Graph Theory and Perfect Graphs".

Category:Graph families
Category:Intersection classes of graphs
Category:Perfect graphs

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