Enumerating Labeled Graphs that Realize a Fixed Degree Sequence

Publication date 6 January 2021

Exact enumeration problems, generating functions (05A15) Enumeration in graph theory (05C30)

Abstract: A finite non-increasing sequence of positive integers

d = (d_{1} g e q c d o t s g e q d_{n})

is called a degree sequence if there is a graph

G = (V, E)

with

V = v_{1}, l d o t s, v_{n}

and

d e g (v_{i}) = d_{i}

for

i = 1, l d o t s, n

. In that case we say that the graph

G

realizes the degree sequence

d

. We show that the exact number of labeled graphs that realize a fixed degree sequence satisfies a simple recurrence relation. Using this relation, we then obtain a recursive algorithm for the exact count. We also show that in the case of regular graphs the complexity of our algorithm is better than the complexity of the same enumeration that uses generating functions.

This page was built for publication: Enumerating Labeled Graphs that Realize a Fixed Degree Sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6357750)