skip to content

Graphical partitions

Monday 25th February 2008 - 11:00 to 12:00
INI Discussion Room

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