# Enumeration of the degree
sequences of non-separable graphs and connected graphs

**Meeting Time:** Nov. 2, 2010, 2:00-2:50pm

**Abstract:**
In 1962, S. L. Hakimi proved necessary and sufficient conditions for a
given sequence of positive integers d_1, d_2, ..., d_n to be the degree
sequence of a non-separable graph or that of a connected graph. Our goal
in this talk is to utilize Hakimi's results to provide generating
functions for the functions d_{ns}(2m) and d_c(2m), the number of degree
sequences with degree sum 2m representable by non-separable graphs and
connected graphs (respectively). From these generating functions, we prove
nice formulas for d_{ns}(2m) and d_c(2m) which are simple linear
combinations of the values of p(j), the number of integer partitions of j.
The proofs are elementary and the talk will be accessible to a wide
audience. This is joint work with Oystein Rodseth and Helge Tverberg, both
from the University of Bergen, Norway.