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

%I #11 Sep 01 2024 19:36:20

%S 1,1,1,1,1,1,2,3,5,9,17,33,73,174,364,759,1859,4177,8715,21053,49119,

%T 113956,269059,711124,1750732

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

%H Samuel Stern, <a href="http://wesscholar.wesleyan.edu/etd_hon_theses/1807">The Tree of Trees: on methods for finding all non-isomorphic tree-realizations of degree sequences</a>, Honors Thesis, Wesleyan University, 2017.

%e 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]

%o (Sage) # from _Max Alekseyev_, Jul 22 2024

%o from collections import Counter

%o a295637 = lambda n: max( Counter(tuple(sorted(T.degree())) for T in graphs.trees(n)).values() )

%K nonn,more

%O 0,7

%A _Eric M. Schmidt_, Nov 25 2017

%E a(19)-a(24) from _Max Alekseyev_, Jul 22 2024