Journal of Combinatorics

Volume 8 (2017)

Number 2

Enumeration of constrained subtrees of trees

Pages: 371 – 387

DOI: https://dx.doi.org/10.4310/JOC.2017.v8.n2.a8

Authors

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.)

Abstract

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.

Keywords

tree, subtree, enumeration

Published 14 February 2017