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

Øystein J. Rødseth, James A. Sellers, Helge Tverberg

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

In 1962, S. L. Hakimi proved necessary and sufficient conditions for a given sequence of positive integers d1, d2, ..., dn to be the degree sequence of a non-separable graph or that of a connected graph. Our goal in this note is to utilize these results to prove closed formulas for the functions dn s (2 m) and dc (2 m), the number of degree sequences with degree sum 2 m representable by non-separable graphs and connected graphs (respectively). Indeed, we give both generating function proofs as well as bijective proofs of the following identities: dn s (2 m) = p (2 m) - p (2 m - 1) - underover(∑, j = 0, m - 2) p (j) and dc (2 m) = p (2 m) - p (m - 1) - 2 underover(∑, j = 0, m - 2) p (j) where p (j) is the number of unrestricted integer partitions of j.

Original languageEnglish (US)
Pages (from-to)1309-1317
Number of pages9
JournalEuropean Journal of Combinatorics
Volume30
Issue number5
DOIs
StatePublished - Jul 2009

Fingerprint Dive into the research topics of 'Enumeration of the degree sequences of non-separable graphs and connected graphs'. Together they form a unique fingerprint.

Cite this