A295637 Maximum k such that there are k nonisomorphic n-vertex trees with the same degree sequence.

1, 1, 1, 1, 1, 1, 2, 3, 5, 9, 17, 33, 73, 174, 364, 759, 1859, 4177, 8715, 21053, 49119, 113956, 269059, 711124, 1750732

Offset

0,7

Links

Table of n, a(n) for n=0..24.

Samuel Stern, The Tree of Trees: on methods for finding all non-isomorphic tree-realizations of degree sequences, Honors Thesis, Wesleyan University, 2017.

Example

There are 2 nonisomorphic trees with degree sequence [1, 1, 1, 2, 2, 3]. It is impossible to improve on this, so a(6) = 2. [Stern, p. 39]

Prog

(Sage) # from Max Alekseyev, Jul 22 2024
from sage.graphs.trees import TreeIterator
from collections import Counter
a295637 = lambda n: max( Counter(tuple(sorted(T.degree())) for T in TreeIterator(n)).values() )

Crossrefs

Sequence in context: A000051 A094373 A213705 * A061902 A166286 A179807

Adjacent sequences: A295634 A295635 A295636 * A295638 A295639 A295640

Keyword

nonn,more

Author

Eric M. Schmidt, Nov 25 2017

Extensions

a(19)-a(24) from Max Alekseyev, Jul 22 2024

Status

approved