Split Graph

A split graph is a graph whose vertices can be partitioned into a clique and an independent vertex set.

Equivalently, it is a chordal graph whose graph complement is also chordal (Royle 2000). Royle (2000) also proved that there is a one-one correspondence between the split graphs on  vertices and the minimal covers of a set of size .

Classes of graphs that are split include complete , empty , star, and sun graphs.

Since all chordal graphs are perfect, so too are all split graphs.

Let  be the degree sequence of a graph on  vertices, and let  be the largest value of  such that . Then the graph is a split graph iff

Furthermore, for a graph satisfying this condition, the vertices corresponding to the first  degrees in the degree sequence correspond to a maximum clique and the remainder to an independent vertex set (Golumbic 1980, Hammer and Simeone 1981).

The numbers of simple split graphs on , 2, ... vertices are given by 1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... (OEIS A048194).

REFERENCES

Golumbic, M. C. Algorithmic Graph Theory and Perfect Graphs. New York: Academic Press, 1980.

Hammer, P. L. and Simeone, B. "The Splittance of a Graph." Combinatorica 1, 275-284, 1981.

Royle, G. F. "Counting Set Covers and Split Graphs." J. Integer Seq. 3, Article 00.2.6, 2000. https://cs.uwaterloo.ca/journals/JIS/VOL3/ROYLE/royle.html.

Sloane, N. J. A. Sequence A048194 in "The On-Line Encyclopedia of Integer Sequences."