Journal of Combinatorics
Volume 8 (2017)
Enumeration of constrained subtrees of trees
Pages: 371 – 387
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