Skip to main content
Article
The Minimal Number of Subtrees of a Tree
Graphs and Combinatorics
  • Andrew V. Sills, Georgia Southern University
  • Hua Wang, Georgia Southern University
Document Type
Article
Publication Date
1-1-2015
DOI
10.1007/s00373-013-1376-y
Disciplines
Abstract

In this note, we consider the trees (caterpillars) that minimize the number of subtrees among trees with a given degree sequence. This is a question naturally related to the extremal structures of some distance based graph invariants. We first confirm the expected fact that the number of subtrees is minimized by some caterpillar. As with other graph invariants, the specific optimal caterpillar is nearly impossible to characterize and depends on the degree sequence. We provide some simple properties of such caterpillars as well as observations that will help finding the optimal caterpillar.

Citation Information
Andrew V. Sills and Hua Wang. "The Minimal Number of Subtrees of a Tree" Graphs and Combinatorics Vol. 31 Iss. 1 (2015) p. 255 - 264 ISSN: 1435-5914
Available at: http://works.bepress.com/hua_wang/55/