- Split graph
In

graph theory , a**split graph**is a graph in which the vertices can be partitioned into a clique and anindependent set . Split graphs were first studied by Földes and Hammer in two papers in 1977, and independently introduced by Tyshkevich and Chernyak (1979). [*Földes and 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 complements of bipartite graphs (that is, graphs that can be partitioned into two cliques). Földes and Hammer (1977b) use the definition given here, which has been followed in the subsequent literature; for instance, it is Brandstädt et al. (1999), Definition 3.2.3, p.41.Note that the partition into a clique and an independent set need not be unique; for instance, the path "a"–"b"–"c" is a split graph, the vertices of which can be partitioned in three different ways:

#the clique {"a","b"} and the independent set {"c"}

#the clique {"b","c"} and the independent set {"a"}

#the clique {"b"} and the independent set {"a","c"}Split graphs can be characterized in terms of their

induced subgraph s: a graph is split if and only if no induced subgraph is a cycle on four or five vertices, or a pair of disjoint edges (the complement of a 4-cycle). [*Földes and Hammer (1977a); Golumbic (1980), Theorem 6.3, p. 151.*]**Relation to other graph families**From the definition, split graphs are clearly closed under complementation. [

*Golumbic (1980), Theorem 6.1, p. 150.*] Another characterization of split graphs involves complementation: they arechordal graph s the complements of which are also chordal. [*Földes and Hammer (1977a); Golumbic (1980), Theorem 6.3, p. 151; Brandstädt et al. (1999), Theorem 3.2.3, p. 41.*] Just as chordal graphs are theintersection graph s of subtrees of trees, split graphs are the intersection graphs of distinct substars of stars. [*McMorris and Shier (1983); Voss (1985); Brandstädt et al. (1999), Theorem 4.4.2, p. 52.*]Almost all chordal graphs are split graphs, as Bender et al. (1985) showed; that is, in the limit as "n" goes to infinity, the fraction of "n"-vertex chordal graphs that are split approaches one. Because chordal graphs are perfect, so are the split graphs; thedouble split graph s, 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 Chudnovsky et al. (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 acomparability 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. [*Földes and Hammer (1977b); Golumbic (1980), Theorem 9.7, page 212.*] The splitcograph s are exactly thethreshold graph s, and the splitpermutation graph s are exactly the interval graphs that have interval graph complements. [*Brandstädt et al. (1999), Corollary 7.1.1, p. 106, and Theorem 7.1.2, p. 107.*] Split graphs have cochromatic number 2.**Maximum clique and maximum independent set**Let "G" be a split graph, partitioned into a clique "C" and an independent set "I". Then every

maximal clique in a split graph is either "C" itself, or the neighborhood of a vertex in "I". Thus, it is easy to identify the maximum clique, and complementarily themaximum independent set in a split graph. In any split graph, one of the following three possibilities must be true: [*Hammer and Simeone (1981); Golumbic (1980), Theorem 6.2, p. 150.*]

# There exists a vertex "x" in "I" such that "C" ∪ {"x"} is complete. In this case, "C" ∪ {"x"} is a maximum clique and "I" is a maximum independent set.

# There exists a vertex "x" in "C" such that "I" ∪ {"x"} is independent. In this case, "I" ∪ {"x"} is a maximum independent set and "C" is a maximum clique.

# "C" is a maximal clique and "I" is a maximal independent set. In this case, "G" has a unique partition ("C","I") into a clique and an independent set, "C" is the maximum clique, and "I" is the maximum independent set.Some other optimization problems that are

NP-complete on more general graph families, includinggraph coloring , are similarly straightforward on split graphs.**Degree sequences**One remarkable property of split graphs is that they can be recognized solely from the sequence of degrees of each vertex. That is, suppose that two graphs have the property that, for each "i", both graphs have equally many vertices with "i" neighboring edges; then either both graphs are split or both are not split. More precisely, sort the degrees of the vertices in a graph "G" into the ordered sequence "d"

_{1}≥ "d"_{2}≥ ... ≥ "d"_{"n"}, and let "m" be the largest value of "i" such that "d"_{"i"}≥ "i" - 1. Then "G" is a split graph if and only if:$sum\_\{i=1\}^m\; d\_i\; =\; m(m-1)\; +\; sum\_\{i=m+1\}^n\; d\_i.$If this is the case, then the "m" vertices with the largest degrees form a maximum clique in "G", and the remaining vertices complete a partition into a clique and an independent set. [*Hammer and Simeone (1981); Tyshkevich (1980); Tyshkevich, Melnikow, and Kotov (1981); Golumbic (1980), Theorem 6.7 and Corollary 6.8, p. 154; Brandstädt et al. (1999), Theorem 13.3.2, p. 203. Merris (2003) further investigates the degree sequences of split graphs.*]**Counting split graphs**Royle (2000) showed that split graphs with "n" unlabeled vertices are in one-to-one correspondence with certain Sperner families. Using this correspondence, he was able to determine a formula for the number of 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 result was independently proved earlier by Tyshkevich and Chernyak in 1990 (in Russian).

**Notes****References**

*cite journal

author = Bender, E. A.; Richmond, L. B.; Wormald, N. C.

title = Almost all chordal graphs split

journal = J. Austral. Math. Soc., Series A

volume = 38

year = 1985

issue = 2

id = MathSciNet | id = 0770128

pages = 214–221*cite book

author = Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy

title = Graph Classes: A Survey

publisher = SIAM Monographs on Discrete Mathematics and Applications

year = 1999

id = ISBN 0-89871-432-X*cite journal

author = Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin

title = The strong perfect graph theorem

journal = Annals of Mathematics

volume = 164

year = 2006

issue = 1

pages = 51–229

url = http://projecteuclid.org/getRecord?id=euclid.annm/1157656789

id = MathSciNet | id = 2233847*cite conference

author = Földes, Stéphane; Hammer, Peter L.

title = Split graphs

booktitle = Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977)

pages = 311–315

publisher = Congressus Numerantium, No. XIX, Utilitas Math.

location = Winnipeg

date = 1977a

id = MathSciNet | id = 0505860*cite journal

author = Földes, Stéphane; Hammer, Peter L.

title = Split graphs having Dilworth number two

journal = Canad. J. Math.

volume = 29

year = 1977b

issue = 3

pages = 666–672

id = MathSciNet | id = 0463041

*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.*cite journal

author = Hammer, Peter L.; Simeone, Bruno

title = The splittance of a graph

journal = Combinatorica

volume = 1

year = 1981

issue = 3

pages = 275–284

id = MathSciNet | id = 0637832

doi = 10.1007/BF02579333*cite journal

author = McMorris, F. R.; Shier, D. R.

title = Representing chordal graphs on "K"_{1,"n"}

journal = Comment. Math. Univ. Carolin.

volume = 24

year = 1983

pages = 489–494*cite journal

author = Merris, Russell

title = Split graphs

journal = European J. Combin.

volume = 24

year = 2003

issue = 4

pages = 413–430

doi = 10.1016/S0195-6698(03)00030-1

id = MathSciNet | id = 1975945*cite journal

author = Royle, Gordon F.

title = Counting set covers and split graphs

journal = Journal of Integer Sequences

volume = 3

year = 2000

issue = 2

pages = 00.2.6

id = MathSciNet | id = 1778996

url = http://www.emis.ams.org/journals/JIS/VOL3/ROYLE/royle.pdf*cite journal

author = Tyshkevich, R. I.

title = The canonical decomposition of a graph

format = In Russian

journal = Doklady Akad. Nauk BSSR

volume = 24

year = 1980

pages = 677–679*cite journal

author = Tyshkevich, R. I.; Chernyak, A. A.

title = Canonical partition of a graph defined by the degrees of its vertices

format = In Russian

year = 1979

journal = Isv. Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk

volume = 5

pages = 14–26*cite journal

author = Tyshkevich, R. I.; Chernyak, A. A.

title = One more method of enumeration of unlabeled combinatorial objects

format = In Russian

year = 1990

journal = Matem. Zametki

volume = 48

pages = 98–105*cite journal

author = Tyshkevich, R. I.; Melnikow, O. I.; Kotov, V. M.

title = On graphs and degree sequences: the canonical decomposition

format = In Russian

journal = Kibernetica

volume = 6

year = 1981

pages = 5–8*cite journal

author = Voss, H.-J.

title = Note on a paper of McMorris and Shier

journal = Comment. Math. Univ. Carolin.

volume = 26

year = 1985

pages = 319–322

*Wikimedia Foundation.
2010.*