The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

CSM

Seminar

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

Sellers, J (Penn State)
Wednesday 02 April 2008, 14:00-15:00

Seminar Room 2, Newton Institute Gatehouse

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 connnected 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, University of Bergen, Norway.

Related Links

Back to top ∧