1
$\begingroup$

Does anyone know if there is currently any research or any potential bounds on the number of trees on $n$ vertices with degree at most $3$? One can bound this above by $C_{n}$ the $n$th Catalan number, or $n^{n-2}$ from Cayley's formula, but I think I have found a way to bound it a little better. I just want to make sure I'm not overlooking something that has already been done.

Edit: Some motivation might be nice? I'm looking at these as dual graphs of triangulations of polygons. I'm trying to see if this could be used to establish a lower bound on the number of unlabeled triangulations of an $(n+2)$-gon.

$\endgroup$

1 Answer 1

3
$\begingroup$

I'm not sure if this specific problem has been done, but the enumeration of unlabeled trees with degree restrictions (especially in connection with chemical compounds) can be found in Pólya's original paper on "Pólya theory", which is available in English translation as G. Pólya and R. C. Read, Combinatorial enumeration of groups, graphs, and chemical compounds, Springer-Verlag New York, 1987. A more modern approach to unlabeled tree enumeration can be found in François Bergeron, Gilbert Labelle, and Pierre Leroux, Combinatorial Species and Tree-like Structures (Encyclopedia of Mathematics and its Applications volume 67), Cambridge University Press, 1998. For more on asymptotics for unlabeled trees of various sorts, see Frank Harary, Robert W. Robinson,and Allen J. Schwenk, "Twenty-step algorithm for determining the asymptotic number of trees of various species", J. Austral. Math. Soc. Ser. A 20 (1975), 483–503.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.