View source for Split graph

{{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)}}
[[File:Split graph.svg|thumb|240px|A split graph, partitioned into a clique and an independent set.]]

In [[graph theory]], a branch of mathematics, a '''split graph''' is a [[Graph (discrete mathematics)|graph]] in which the [[Vertex (graph theory)|vertices]] can be [[Graph partition|partitioned]] into a [[clique (graph theory)|clique]] and an [[Independent set (graph theory)|independent set]]. 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]]s (that is, graphs that be partitioned into two independent sets) and the [[complement (graph theory)|complements]] 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 graph|path]] {{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]]s: a graph is split if and only if no [[induced subgraph]] is a [[cycle graph|cycle]] 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 [[complement (graph theory)|complementation]].<ref>{{harvtxt|Golumbic|1980}}, Theorem 6.1, p. 150.</ref> Another characterization of split graphs involves complementation: they are [[chordal graph]]s the [[complement (graph theory)|complements]] 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]]s of subtrees of trees, split graphs are the intersection graphs of distinct substars of [[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]] 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 graph|perfect]], 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]].

If a graph is both a split graph and an [[interval graph]], then its complement is both a split graph and a [[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]]s are exactly the [[threshold graph]]s. The split [[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]]s.{{sfnp|Kézdy|Snevily|Wang|1996}} Split graphs have [[cocoloring|cochromatic number]] 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]] in a split graph is either {{mvar|C}} itself, or the [[neighborhood (graph theory)|neighborhood]] of a vertex in {{mvar|i}}. Thus, it is easy to identify the maximum clique, and complementarily the [[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]] on more general graph families, including [[graph coloring]], are similarly straightforward on split graphs. Finding a [[Hamiltonian cycle]] remains [[NP-complete]] even for split graphs which are [[strongly chordal graph]]s.<ref>{{harvtxt|Müller|1996}}</ref> It is also well known that the Minimum Dominating Set problem remains [[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]]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]] 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 ([[Graph labeling|unlabeled]]) ''n''-vertex split graphs are in [[one-to-one correspondence]] with certain [[Sperner families]]. Using this fact, he  determined a formula for the number of [[graph isomorphism|nonisomorphic]] 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 [[graph enumeration|enumerative]] 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.
 | series = A
 | 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]]
 | 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]]
 | 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]]
 | 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]]
 | 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]]
 | 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 (journal)|Discrete Mathematics]]
 | volume = 156
 | year = 1996
 | 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]]
 | 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]], "Algorithmic Graph Theory and Perfect Graphs".

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