Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Parameters of a random rooted tree
Rakotoniaina, Fameno. 2024. Parameters of a random rooted tree. Unpublished masters dissertation. Stellenbosch : Stellenbosch University [online]. Available: https://scholar.sun.ac.za/handle/10019.1/131894 Thesis (MSc)--Stellenbosch University, 2024.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Stellenbosch : Stellenbosch University
2025
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867614087936999424 |
|---|---|
| access_status_str | Open Access |
| author | Rakotoniaina, Fameno |
| author2 | Ralaivaosaona, Dimbinaina
|
| author_browse | Rakotoniaina, Fameno Ralaivaosaona, Dimbinaina |
| author_facet | Ralaivaosaona, Dimbinaina
Rakotoniaina, Fameno |
| author_sort | Rakotoniaina, Fameno |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Rakotoniaina, Fameno. 2024. Parameters of a random rooted tree. Unpublished masters dissertation. Stellenbosch : Stellenbosch University [online]. Available: https://scholar.sun.ac.za/handle/10019.1/131894
Thesis (MSc)--Stellenbosch University, 2024. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/131894 |
| institution | Stellenbosch University (South Africa) |
| last_indexed | 2026-06-10T12:46:28.519Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2025 |
| publishDateRange | 2025 |
| publishDateSort | 2025 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/131894 Parameters of a random rooted tree Rakotoniaina, Fameno Ralaivaosaona, Dimbinaina Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Galton-Watson trees -- Mathematical models Algorithms Binary system (Mathematics) Trees (Graph theory) -- Mathematical models Additive functions UCTD Rakotoniaina, Fameno. 2024. Parameters of a random rooted tree. Unpublished masters dissertation. Stellenbosch : Stellenbosch University [online]. Available: https://scholar.sun.ac.za/handle/10019.1/131894 Thesis (MSc)--Stellenbosch University, 2024. ENGLISH ABSTRACT: Let T denote the Galton-Watson tree with offspring distribution ξ, and let Tn be the Galton-Watson tree conditioned to have exactly n nodes. We assume that the offspring distribution ξ satisfies E(ξ) = 1 and 0 < Varξ < ∞. We study the distribution of three tree parameters, namely, the independence number, the domination number, and the total domination number in the conditioned Galton-Watson model. We show that these tree parameters are asymptotically normal as the order of the tree tends to infinity. Our method is based on the analysis of bottom-up algorithms that are able to compute these quantities for trees. From these algorithms, we can construct tree additive functionals whose toll functions are almost local. Then, we apply a recent result on the central limit theorem for additive functionals with almost local toll functions. Furthermore, while addressing an open problem in a recent paper by Janson, we show, under a mild condition on the moments of ξ, that the number of copies of a fixed rooted plane tree t as general subtrees of Tn has a mean linear in n and a variance at most linear in n. AFRIKAANSE OPSOMMING: Laat T die Galton-Watson-boom voorstel met nageslagverdeling ξ, en Tn die Galton-Watson-boom wees wat gekondisioneer is om presies n nodusse te hˆe. Ons neem aan dat die nageslagverdeling ξ voldoen aan E(ξ) = 1 en 0 < Varξ < ∞. Ons bestudeer die verspreiding van drie boomparameters, naamlik die onafhanklikheidsgetal, die dominasienommer, en die totale do- minasienommer in die gekondisioneerde Galton-Watson-model. Ons wys dat hierdie boomparameters asimptoties normaal is soos die orde van die boom tot oneindig neig. Ons metode is gebaseer op die analise van “bottom-up- algoritmes wat in staat is om hierdie hoeveelhede vir bome te bereken. Uit hierdie algoritmes kan ons boomadditiewe funksionale konstrueer waarvan die tolfunksies amper plaaslik is. Dan pas ons ’n onlangse resultaat toe oor die sentrale-limietstelling vir additiewe funksionale met amper plaaslike tolfunk- sies. Verder, terwyl ons ’n ope vraag in ’n onlangse artikel deur Janson aan- spreek, wys ons, onder ’n swakker kondisie die momente van ξ, dat die aantal kopie¨e van ’n vaste gewortelde platboom t as algemene subbome van Tn ’n gemiddelde het wat lineˆer in n is en ’n variansie wat hoogstens lineˆer in n is. Masters 2025-04-07T13:02:37Z 2025-04-07T13:02:37Z 2024-12 Thesis https://scholar.sun.ac.za/handle/10019.1/131894 Stellenbosch University xi, 77 pages application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Galton-Watson trees -- Mathematical models Algorithms Binary system (Mathematics) Trees (Graph theory) -- Mathematical models Additive functions UCTD Rakotoniaina, Fameno Parameters of a random rooted tree |
| title | Parameters of a random rooted tree |
| title_full | Parameters of a random rooted tree |
| title_fullStr | Parameters of a random rooted tree |
| title_full_unstemmed | Parameters of a random rooted tree |
| title_short | Parameters of a random rooted tree |
| title_sort | parameters of a random rooted tree |
| topic | Galton-Watson trees -- Mathematical models Algorithms Binary system (Mathematics) Trees (Graph theory) -- Mathematical models Additive functions UCTD |
| url | https://scholar.sun.ac.za/handle/10019.1/131894 |
| work_keys_str_mv | AT rakotoniainafameno parametersofarandomrootedtree |