Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
The number of different types of dominating sets in binary trees
Oyewumi, Opeyemi. 2024. The number of different types of dominating sets in binary trees. Unpublished doctoral dissertation. Stellenbosch : Stellenbosch University [online]. Available: https://scholar.sun.ac.za/handle/10019.1/131880 Thesis (PhD)--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_ | 1867613929411182592 |
|---|---|
| access_status_str | Open Access |
| author | Oyewumi, Opeyemi |
| author2 | Roux, A. |
| author_browse | Oyewumi, Opeyemi Roux, A. |
| author_facet | Roux, A. Oyewumi, Opeyemi |
| author_sort | Oyewumi, Opeyemi |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Oyewumi, Opeyemi. 2024. The number of different types of dominating sets in binary trees. Unpublished doctoral dissertation. Stellenbosch : Stellenbosch University [online].
Available: https://scholar.sun.ac.za/handle/10019.1/131880
Thesis (PhD)--Stellenbosch University, 2024. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/131880 |
| institution | Stellenbosch University (South Africa) |
| last_indexed | 2026-06-10T12:43:57.159Z |
| 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/131880 The number of different types of dominating sets in binary trees Oyewumi, Opeyemi Roux, A. Wagner, Stephan Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Binary system (Mathematics) Domination (Graph theory) Trees (Graph theory) -- Mathematical models Number theory Binary trees -- Data processing -- Mathematical models UCTD Oyewumi, Opeyemi. 2024. The number of different types of dominating sets in binary trees. Unpublished doctoral dissertation. Stellenbosch : Stellenbosch University [online]. Available: https://scholar.sun.ac.za/handle/10019.1/131880 Thesis (PhD)--Stellenbosch University, 2024. ENGLISH ABSTRACT: An (unrooted) binary tree is a tree in which every internal vertex has degree 3. More generally, if all internal vertices of a tree are exactly of degree d + 1, it is known as a d-ary tree. A subset D of the vertex set of a graph G is a dominating set of G if every vertex in V (G) \ D has a neighbour in D. A dominating set D of G is a total dominating set of G if every vertex in D has a neighbour in D as well. And a dominating set D of G is an independent dominating set of G if no vertex of D has a neighbour in D. This dissertation focuses on determining the number of three different types of dominating sets; namely, (ordinary) dominating sets, total dominating sets and independent dominating sets, in binary trees, and more generally d-ary trees. The corresponding extremal binary (d-ary) trees are also characterized. The minimum number of dominating sets in d-ary trees is always attained by the d-ary caterpillar. We determine the maximum number of dominating sets in binary trees, the binary trees that attain the maximum are unique. The minimum number of total dominating sets in binary trees is always attained by the binary caterpillar, and the binary trees that attain the maximum are only unique when the number of vertices is not divisible by 4. We obtain a lower bound on the number of total dominating sets for d-ary trees and characterized the extremal trees as well. The minimum, second largest and maximum number of independent dom- inating sets (equivalently, maximal independent sets) in binary trees of a given order are determined. A characterization of the extremal binary trees are also determined. The minimum is attained uniquely by the binary cater- pillar while the binary trees that attain the maximum are also unique. AFRIKAANSE OPSOMMING: ’n Binêre boom (sonder ’n wortel) is ’n boom waarin elke interne nodus graad 3 het. Meer algemeen, as alle interne nodusse van ’n boom presies graad d + 1 het, staan dit bekend as ’n d-êre boom. ’n Deelversameling D van die nodusversameling van ’n grafiek G is ’n dominasieversameling van G as elke nodus in V (G)\D naasliggend is aan ’n nodus in D. ’n Dominasiever- sameling D van G is ’n totale dominasieversameling van G as elke nodus in D ook naasliggend is aan ’n nodus in D. Verder is ’n dominasieversameling D van G is ’n onafhanklike dominasieversameling van G as geen nodus van D naasliggend is aan ’n ander nodus in D nie. Hierdie proefskrif fokus op die bepaling van die aantal dominasieversamelings vir elk van die drie verskillende tipes dominasieversamelings, naamlik, in bi- nêre bome, en meer algemeen d-êre bome. Die ooreenstemmende ekstreme binêre (d-êre) bome word ook gekarakteriseer. Die minimum aantal dominasieversamelings in d-êre bome word altyd bereik deur die d-êre ruspe. Ons bepaal die maksimum aantal dominasieversame- lings in binêre bome, die binêre bome wat die maksimum bereik, is uniek. Die minimum aantal totale dominasieversamelings in binêre bome word altyd bereik deur die binêre ruspe, en die binêre bome wat die maksimum bereik, is slegs uniek wanneer die aantal nodusse nie deur 4 deelbaar is nie. Ons bepaal ’n ondergrens vir die aantal totale dominasieversamelings vir d-êre bome en karakteriseer ook die ekstreme bome. Die minimum, tweede grootste en maksimum aantal onafhanklike domina- sieversamelings (ekwivalent, maksimale onafhanklike versamelings) in binêre bome van ’n gegewe orde word bepaal. ’n Karakterisering van die ekstreme binêre bome word ook bepaal. Die minimum word uniek bereik deur die binêre ruspe terwyl die binêre bome wat die maksimum bereik, ook uniek is. Doctoral 2025-04-07T06:50:34Z 2025-04-07T06:50:34Z 2024-12 Thesis https://scholar.sun.ac.za/handle/10019.1/131880 Stellenbosch University xiii, 94 pages : illustrations application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Binary system (Mathematics) Domination (Graph theory) Trees (Graph theory) -- Mathematical models Number theory Binary trees -- Data processing -- Mathematical models UCTD Oyewumi, Opeyemi The number of different types of dominating sets in binary trees |
| title | The number of different types of dominating sets in binary trees |
| title_full | The number of different types of dominating sets in binary trees |
| title_fullStr | The number of different types of dominating sets in binary trees |
| title_full_unstemmed | The number of different types of dominating sets in binary trees |
| title_short | The number of different types of dominating sets in binary trees |
| title_sort | number of different types of dominating sets in binary trees |
| topic | Binary system (Mathematics) Domination (Graph theory) Trees (Graph theory) -- Mathematical models Number theory Binary trees -- Data processing -- Mathematical models UCTD |
| url | https://scholar.sun.ac.za/handle/10019.1/131880 |
| work_keys_str_mv | AT oyewumiopeyemi thenumberofdifferenttypesofdominatingsetsinbinarytrees AT oyewumiopeyemi numberofdifferenttypesofdominatingsetsinbinarytrees |