Split graph

A split graph, partitioned into a clique and an independent set.

In graph theory, 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 Földes and Hammer in two papers in 1977.

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:

1. the clique {a,b} and the independent set {c}
2. the clique {b,c} and the independent set {a}
3. the clique {b} and the independent set {a,c}

Split graphs can be characterized in terms of their induced subgraphs: 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).

Relation to other graph families

From the definition, split graphs are clearly closed under complementation. Another characterization of split graphs involves complementation: they are chordal graphs the complements of which are also chordal. Bender et al. (1985) showed that, in the limit as n goes to infinity, the fraction of chordal graphs that are split approaches one. As a subclass of chordal graphs, split graphs are perfect, and the double split graphs, a family of graphs derived from split graphs by doubling every vertex, 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 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.

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 the maximum independent set in a split graph. In any split graph, one of the following three possibilities must be true:

1. 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.
2. 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 clique.
3. 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.

Other optimization problems that are NP-complete on more general graph families, including the minimum dominating set and graph coloring problems, 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, if two graphs have the same degree sequence, they are either both split or both not split. More precisely, suppose that a graph G has vertices with degrees d₁ ≥ d₂ ≥ ... ≥ 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. 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, ... (sequence A048194 in the OEIS).

References

• Bender, E. A.; Richmond, L. B.; Wormald, N. C. (1985). "Almost all chordal graphs split". J. Austral. Math. Soc., Series A. 38 (2). MR0770128. {{cite journal}}: Text "214–221" ignored (help)CS1 maint: multiple names: authors list (link)

• Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006). "The strong perfect graph theorem". Annals of Mathematics. 164 (1): 51–229. MR2233847.{{cite journal}}: CS1 maint: multiple names: authors list (link)

• Földes, Stéphane; Hammer, Peter L. (1977a). "Split graphs". Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977). Winnipeg: Congressus Numerantium, No. XIX, Utilitas Math. pp. 311–315. MR0505860. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)CS1 maint: multiple names: authors list (link)

• Földes, Stéphane; Hammer, Peter L. (1977b). "Split graphs having Dilworth number two". Canad. J. Math. 29 (3): 666–672. MR0463041.{{cite journal}}: CS1 maint: multiple names: authors list (link)

• Golumbic, Martin Charles (1980). Algorithmic Graph Theory and Perfect Graphs. Academic Press. ISBN 0-12-289260-7.

• Hammer, Peter L.; Simeone, Bruno (1981). "The splittance of a graph". Combinatorica. 1 (3): 275–284. MR0637832.{{cite journal}}: CS1 maint: multiple names: authors list (link)

• Merris, Russell (2003). "Split graphs". European J. Combin. 24 (4): 413–430. doi:10.1016/S0195-6698(03)00030-1. MR1975945.

• Royle, Gordon F. (2000). "Counting set covers and split graphs" (PDF). Journal of Integer Sequences. 3 (2): 00.2.6. MR1778996.