Properties of greedy trees

[摘要] ENGLISH ABSTRACT: A greedy tree is constructed from a given degree sequence using a simplegreedy algorithm that assigns the highest degree to the root, the second,the third, . . . , -highest degree to the root's neighbours, etc. This particulartree is the solution to numerous extremal problems among all trees withgiven degree sequence. In this thesis, we collect results for some distancebasedgraph invariants, the number of subtrees and the spectral radiusin which greedy trees play a major role. We show that greedy trees areextremal for the aforementioned graph invariants by means of two differentapproaches, one using level greedy trees and majorization, while the otherone is somewhat more direct. Finally, we prove some new results on greedytrees for additive parameters with specific toll functions.

[发布机构] Stellenbosch University