Trees with given degree sequences that have minimal subtrees

Xiu-Mei Zhang, Xiao-Dong Zhang

Published 2012-09-03Version 1

In this paper, we investigate the structures of an extremal tree which has the minimal number of subtrees in the set of all trees with the given degree sequence of a tree. In particular, the extremal trees must be caterpillar and but in general not unique. Moreover, all extremal trees with a given degree sequence $\pi=(d_1, ..., d_5, 1,..., 1)$ have been characterized.