hide
Free keywords:
-
Abstract:
A non-decreasing sequence of n integers is the degree sequence of a 1-tree
(i.e., an ordinary tree) on n vertices if and only if there are least two 1’s
in the sequence, and the sum of the elements is 2(n–1). We generalize this
result in the following ways. First, a natural generalization of this statement
is a necessary condition for k-trees, and we show that it is not sufficient for
any k > 1. Second, we identify non-trivial sufficient conditions for the degree
sequences of 2-trees. We also show that these sufficient conditions are almost
necessary using bounds on the partition function p(n) and probabilistic
methods. Third, we generalize the characterization of degrees of 1-trees in an
elegant and counter-intuitive way to yield integer sequences that characterize
k-trees, for all k.
