Page 120 - Textos de Matemática Vol. 39

110 RUSSELL MERRIS
Proof of Theorem 2.1. Let σ = (σ1, σ2, . . . , σn) be an arbitrary split parti- tion of 2m ≥ 6, so that both ρ(σ) and β(σ) are (strict) partitions of m. Suppose firstthatσ2 >1,sothatf(σ)≥2. th
By successively moving boxes from rows below the f(σ) down, if neces- sary, F (σ) can be transformed into the Ferrers diagram of a new split partition, callitν,suchthatνi =1foralli>f(ν)=f(σ).
Because ν1 ≥ ν2 ≥ ··· ≥ νf(ν), by successively moving boxes down in its first f(ν) rows if necessary, F(ν) can be transformed into the Ferrers diagram of yet another split partition, τ , such that τ1 − τf (τ ) ≤ 1, i.e., so that the lengths of the first f(τ) = f(ν) rows of F(τ) are as close to equal as possible. Note that τ is a minimal split partition. No (further) boxes can be moved down in F(τ) if the result is to be the Ferrers diagram of a split partition. Moreover, because F(τ) was obtained from F(σ) by moving boxes down, σ ≻ τ.
If f(σ) = 1, then σ = (m,1m) and σ ≻ 1mu = (m−1,2,1m−1). Applying the previous arguments to μ, one again obtains a minimal split partition τ such that l(τ) = 2 and σ ≻ τ.
It remains to prove that any graph realizing τ is of the type described in the conclusion of Theorem 2.1. Because τ is a split partition, and split partitions are graphic, there is a (split) graph G = (V,E) that realizes τ, i.e., such that τ = d(G). Let V = W ∪ U be a partitioning of V into the disjoint union of a maximum clique W and an independent set U. By [13, Lemma 6.3], o(W) = f(τ), so U is precisely the set of vertices of G of degree 1 and W = V \ U. That every vertex of W is adjacent to at least one vertex of U is a consequence of the fact that τf(τ) ≥ f(τ) = o(W) > o(W) − 1. Finally, d(w1) − d(w2) ≤ 1 for all w1, w2 ∈ W follows from the identification of W with the vertices of G of degrees greater than 1, and the fact that d(G) = τ.
3. Self Complementary Split Graphs.
Because induced subgraphs isomorphic to 2K2 are forbidden, a split graph can have at most one nontrivial component. Together with the fact that, apart from K1, every connected threshold graph has a dominating vertex, this implies that no threshold graph on n > 1 vertices is self complementary. On the other hand, every self complementary chordal graph is split. It is the main purpose of this section explicitly to describe four infinite families of self complementary split graphs.
Recall, for a graph on n vertices to have an isomorphic complement it is necessary that n ≡ 0 or 1 (mod 4). Consider first the case n = 4q,q ≥ 1. Let W = {w1,w2,...,w2q} and U = {u1,u2,...,u2q} be disjoints sets of 2q vertices each.