Page 117 - Textos de Matemática Vol. 39

OBSERVATIONS CONCERNING SPLIT GRAPHS
RUSSELL MERRIS
Dedicated to Eduardo Marques de Sa´.
Abstract. This note continues the author’s investigation of split graphs with special emphasis on their Laplacian matrices.
1. Introduction.
Let G = (V, E) be a graph with vertex set V and edge set E of cardinalities o(V ) = n and o(E) = m, respectively. Denote by dG(v) the degree of vertex v ∈ V , and let d(G) = (d1, d2, ..., dn) be the sequence of these degrees arranged in nonincreasing order, d1 ≥ d2 ≥ ··· ≥ dn. Then, by what has come to be known as the First theorem of graph theory, d(G) is a partition of 2m.
For our present purposes, a nonincreasing sequence π = (π1,π2,...,πl) of nonnegative integers is a partition of r of length l = l(π) if π1 +π2 +· · ·+πl = r. A partition π of 2m (written π ⊢ 2m) is graphic if there is a graph G such that d(G) = π. Such a graph is said to realize π. Among several characterizations of graphic partitions (see, e.g., [18], but beware of typographical errors), the most useful for us involves a variation on the theme of majorization [9].
If μ ⊢ r, ν ⊢ s, r ≥ s, and
k i=1
μi ≥
k i=1
νi , 1 ≤ k ≤ min{l(μ),l(ν)}
then μ weakly submajorizes ν. In the special case that r = s, μ is said to majorize ν, written μ ≻ ν. Majorization is best illustrated by means of so-called Ferrers diagrams. If μ ⊢ r, the diagram F(μ) consists of l(μ) left-justified rows, the
ith of which contains μi “boxes”. (The diagram for μ = (4, 3, 23, 1), short for (4,3,2,2,2,1), is illustrated in Fig. 1.) As a moment’s reflection will show,
2000 Mathematics Subject Classification. 05C07, 05C50, 05C75, 15A36
This work was done during the author’s visiting professorship at Williams College, spring 2006.
107