skip to content

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

Wednesday 2nd April 2008 - 14:00 to 15:00
INI Seminar Room 2

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

University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons