Best possible degree sequence conditions for graph properties
Hajo Broersma ( University of Durham )

16:30 9th March 2010 ( week 8, Hilary Term 2010 )Lecture Theatre B
We discuss recent work on graphical degree sequences, i.e., sequences of integers that correspond to the degrees of the vertices
of a graph. Historically, such degree sequences have been used to provide sufficient conditions for graphs to have a certain
property, such as being kconnected or hamiltonian. For hamiltonicity, this research has culminated in a beautiful
theorem due to Chvátal (1972). This theorem gives a sufficient condition for a graphical degree sequence to be forcibly
hamiltonian, i.e., such that every graph with this degree sequence is hamiltonian. Moreover, the theorem is the strongest
of an entire class of theorems in the following sense: if the theorem does not guarantee that a sequence ∏ is forcibly
hamiltonian, then there exists a nonhamiltonian graph with a degree sequence that majorizes ∏. Kriesell solved an open
problem due to Bauer et al. by establishing similar conditions for kedge connectivity for any fixed k.
We will introduce a general framework for such conditions and discuss recent progress on similar sufficient conditions for
a variety of graph properties. This is based on joint work with Bauer, van den Heuvel, Kahl, and Schmeichel.