Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Education
Greedy Trees, Subtrees And Antichains, Eric Ould Dadah Andriantiana, Stephan G. Wagner, Hua Wang
Greedy Trees, Subtrees And Antichains, Eric Ould Dadah Andriantiana, Stephan G. Wagner, Hua Wang
Department of Mathematical Sciences Faculty Publications
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 …