Mathematics Graduate Students Organization

Seminar:

Date: April 3

The degree sequence of a simple, undirected graph G is the non-increasing sequence of degrees of each vertex of G. One problem that may arise is to determine whether or not a given integer sequence d is graphic - that is, d corresponds to the degree sequence of some graph. Havel and Hakimi proved independently (ca. 1960) that a non-increasing finite sequence d of non-negative integers is graphic if and only if performing a certain sequence of operations on d produces a sequence d’ of all zeros.

A somewhat surprising result, conjectured by Fajtlowicz (1988) and proven independently by Favaron, Maheo and Sacle (1991) and Griggs and Kleitman (1992), is that the number of zeros contained in the sequence d’ of a graphic sequence d, called the residue of d, is a lower bound for the independence number of any graph G for which d is the degree sequence, where the independence number is the cardinality of a largest set of vertices of G with the property that no two vertices in the set are joined by an edge. In this talk I will survey some more recent developments on the residue and its applications to the independence number of a graph, as well as some open problems.