Split graph

[11] It is also well known that the Minimum Dominating Set problem remains NP-complete for split graphs.

[12] One remarkable property of split graphs is that they can be recognized solely from their degree sequences.

[14] Royle (2000) showed that (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 nonisomorphic split graphs on n vertices.

For small values of n, starting from n = 1, these numbers are This enumerative result was also proved earlier by Tyshkevich & Chernyak (1990).