Properties of greedy trees

Description

Thesis (MSc)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: A greedy tree is constructed from a given degree sequence using a simple
greedy algorithm that assigns the highest degree to the root, the second,
the third, . . . , -highest degree to the root’s neighbours, etc. This particular
tree is the solution to numerous extremal problems among all trees with
given degree sequence. In this thesis, we collect results for some distancebased
graph invariants, the number of subtrees and the spectral radius
in which greedy trees play a major role. We show that greedy trees are
extremal for the aforementioned graph invariants by means of two different
approaches, one using level greedy trees and majorization, while the other
one is somewhat more direct. Finally, we prove some new results on greedy
trees for additive parameters with specific toll functions. / AFRIKAANSE OPSOMMING: ’n Gulsige boom word vanuit ’n gegewe graadry deur middel van ’n eenvoudige
gulsige algoritme gebou, wat die hoogste graad aan die wortel
toewys, die tweede-, derde-, . . . , -hoogste graad aan die wortel se bure,
ens. Hierdie spesifieke boom is die oplossing van ’n groot aantal ekstremale
probleme onder al die bome met gegewe graadry. In hierdie tesis
beskou ons ’n versameling van resultate oor afstand-gebaseerde grafiekinvariante,
die aantal subbome en die spektraalstraal waarin gulsige bome
’n belangrike rol speel. Ons bewys dat gulsige bome ekstremaal vir die
bogenoemde grafiekinvariante is deur van twee verskillende tegnieke gebruik
te maak: een met behulp van vlak-gulsige bome en majorering, en
’n ander metode wat effens meer direk is. Laastens bewys ons sommige
nuwe resultate oor gulsige bome vir additiewe parameters met spesifieke
tolfunksies.

Links & Downloads

1. http://hdl.handle.net/10019.1/95909

Tags

Algorithms

Greedy trees

Majorization (Mathematics)

UCTD

Dissertations -- Mathematics

Theses -- Mathematics

Trees (Graph theory)

Additional Fields

Identifer	oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/95909
Date	12 1900
Creators	Razanajatovo Misanantenaina, Valisoa
Contributors	Wagner, Stephan, Stellenbosch University. Faculty of Science. Department of Mathematical Sciences.
Publisher	Stellenbosch : Stellenbosch University
Source Sets	South African National ETD Portal
Language	en_ZA
Detected Language	Unknown
Type	Thesis
Rights	Stellenbosch University