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.
@article{10_37236_3101,
author = {Eric Ould Dadah Andriantiana and Stephan Wagner and Hua Wang},
title = {Greedy trees, subtrees and antichains},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {3},
doi = {10.37236/3101},
zbl = {1295.05076},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3101/}
}
TY - JOUR
AU - Eric Ould Dadah Andriantiana
AU - Stephan Wagner
AU - Hua Wang
TI - Greedy trees, subtrees and antichains
JO - The electronic journal of combinatorics
PY - 2013
VL - 20
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/3101/
DO - 10.37236/3101
ID - 10_37236_3101
ER -
%0 Journal Article
%A Eric Ould Dadah Andriantiana
%A Stephan Wagner
%A Hua Wang
%T Greedy trees, subtrees and antichains
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/3101/
%R 10.37236/3101
%F 10_37236_3101
Eric Ould Dadah Andriantiana; Stephan Wagner; Hua Wang. Greedy trees, subtrees and antichains. The electronic journal of combinatorics, Tome 20 (2013) no. 3. doi: 10.37236/3101
