zbMATH — the first resource for mathematics

Enumeration of constrained subtrees of trees. (English) Zbl 1366.05052
Summary: Starting from the work of L. A. SzĂ©kely and H. Wang [Discrete Math. 322, 36–47 (2014; Zbl 1283.05059); Congr. Numerantium 177, 147–169 (2005; Zbl 1088.05025)], 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.
05C30 Enumeration in graph theory
05C05 Trees
subtree; enumeration
Full Text: DOI