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."

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength