Journal of Combinatorics

Volume 8 (2017)

Number 2

Enumeration of constrained subtrees of trees

Pages: 371 – 387



Hua Wang (Department of Mathematical Sciences, Georgia Southern University, Statesboro, Ga., U.S.A.)

Shuai Yuan (Department of Mathematics, University of South Carolina, Columbia, S.C., U.S.A.)


Starting from the work of Székely and Wang, where the extremal trees and binary trees that maximize or minimize the number of subtrees are characterized, the examination of the numbers of subtrees has been an interesting topic providing applications and questions in Phylogeny reconstruction, Graph Theory, Number Theory, and Computer Science. We present linear-time algorithms for enumerations of subtrees under various constraints. Such specific categories of subtrees including but not limited to those of given orders and those containing vertices of a given set, are of interests due to their applications.


tree, subtree, enumeration

Published 14 February 2017