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:
(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 packagegeng
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):