Greedy Trees, Subtrees and Antichains

  • Eric Ould Dadah Andriantiana
  • Stephan Wagner
  • Hua Wang
Keywords: Greedy trees, Degree sequences, subtrees, antichains

Abstract

Greedy trees are constructed from a given degree sequence by a simple greedy algorithm that assigns the highest degree to the root, the second-, third-, ... highest degrees to the root's neighbors, and so on.

 

They have been shown to maximize or minimize a number of different graph invariants among trees with a given degree sequence. In particular, the total number of subtrees of a tree is maximized by the greedy tree. In this work, we show that in fact a much stronger statement holds true: greedy trees maximize the number of subtrees of any given order. This parallels recent results on distance-based graph invariants.

 

We obtain a number of corollaries from this fact and also prove analogous results for related invariants, most notably the number of antichains of given cardinality in a rooted tree.

Published
2013-08-30
Article Number
P28