Graph Theory – Counting Non-Isomorphic Trees from a Degree Sequence

graph theory

Suppose I have the degree sequence $(5,4,3,2,2,2,1,1,1,1,1,1,1,1)$. This is a tree, and a simple representation is:

enter image description here

(My intuition says that any degree sequence that corresponds to a tree can be laid out like this in a caterpillar. @David demonstrated that is true).

Question:
Is there a good approach to counting all possible non-isomorphic trees that have this degree sequence?

Easier question: (which I would still like to see a good approach for)
How many non-isomorphic caterpillar graphs have this degree sequence?

Best Answer

It looks like there's not going to be a clever way to do this. Using geng 14 13:13 -c (the package geng comes with Nauty), we can generate representatives from each isomorphism class of 14-vertex trees. I wrote a GAP script to identify the ones with the degree sequence [ 5, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1 ]. It turns out there's 150 of them, drawn below (with the vertices ascribed their degrees):

enter image description here

Related Question