Journal of Combinatorics

Volume 3 (2012)

Number 2

Trees with the most subtrees: an algorithmic approach

Pages: 207 – 223

DOI: https://dx.doi.org/10.4310/JOC.2012.v3.n2.a5

Authors

Daniel Gray (Department of Mathematics, University of Florida, Gainesville, Fl., U.S.A.)

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

Xiao-Dong Zhang (Department of Mathematics, Shanghai Jiao Tong University, Shanghai, China)

Xiu-Mei Zhang (Department of Mathematics, Shanghai Jiao Tong University, Shanghai, China)

Abstract

When considering the number of subtrees of trees, the extremal structures which maximize this number among binary trees and trees with a given maximum degree lead to some interesting facts that correlate to other graphical indices in applications. The number of subtrees in the extremal cases constitute sequences which are of interest to number theorists. The structures which maximize or minimize the number of subtrees among general trees, binary trees and trees with a given maximum degree have been identified previously. Most recently, results of this nature are generalized to trees with a given degree sequence. In this note, we characterize the trees which maximize the number of subtrees among trees of a given order and degree sequence. Instead of using theoretical arguments, we take an algorithmic approach that explicitly describes the process of achieving an extremal tree from any random tree. The result also leads to some interesting questions and provides insight on finding the trees close to extremal and their numbers of subtrees.

Keywords

trees, subtrees, extremal

2010 Mathematics Subject Classification

05C05, 05C07, 05C35, 05C85

Full Text (PDF format)

Published 28 September 2012