Page 119 - Textos de Matemática Vol. 39

OBSERVATIONS CONCERNING SPLIT GRAPHS
109

Figure 3
Among the results of [13] is that threshold covered split partitions (the ones illustrated in Fig. 3 using light boxes) are unigraphic. The main result of this section concerns the minimal split partitions.
If μ ⊢ r, denote the number of boxes on the main diagonal of F(μ) by f(μ)=o({i:μi ≥i}).
Theorem 2.1. Suppose G = (V,E) realizes the minimal split partition π ⊢ 2m ≥ 6. If G has no isolated vertices, then V is the disjoint union of sets W and U where o(W ) = f (π); the induced subgraph G[W ] is a clique; U is an independent set; every vertex of U has degree 1 in G; every vertex of W is adjacent to at least one vertex of U; and d(w1)−d(w2) ≤ 1 for all w1,w2 ∈ W.
Graphs that satisfy the conclusions of Theorem 2.1 are among the so- called “hairy cliques”. It is easy to see (alternatively, consult [19]) that hairy cliques are uniquely determined by their degree sequences. So, the following is an immediate consequence of Theorem 2.1.
Corollary 2.2. Apart from isolated vertices, minimal split partitions are uni- graphic.
A minimal split graph is one whose degree sequence is a minimal split partition. Evidently, the complement of a minimal split graph is also uniquely determined by its degree sequence.