Skip to main content

Best possible degree sequence conditions for graph properties

Hajo Broersma ( University of Durham )
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 k-connected 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 k-edge 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.

Share this: