Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Higher order domination of graphs
Thesis (MSc)--University of Stellenbosch, 2004.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : University of Stellenbosch
2011
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867614101512912896 |
|---|---|
| access_status_str | Open Access |
| author | Benecke, Stephen |
| author2 | Van Vuuren, J. H. |
| author_browse | Benecke, Stephen Van Vuuren, J. H. |
| author_facet | Van Vuuren, J. H. Benecke, Stephen |
| author_sort | Benecke, Stephen |
| collection | Thesis |
| dc_rights_str_mv | University of Stellenbosch |
| description | Thesis (MSc)--University of Stellenbosch, 2004. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/16257 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:46:41.344Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2011 |
| publishDateRange | 2011 |
| publishDateSort | 2011 |
| publisher | Stellenbosch : University of Stellenbosch |
| publisherStr | Stellenbosch : University of Stellenbosch |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/16257 Higher order domination of graphs Benecke, Stephen Van Vuuren, J. H. Grobler, P. J. P. University of Stellenbosch. Faculty of Science. Dept. of Mathematical Sciences. Domination (Graph theory) Graph theory Theses -- Applied mathematics Dissertations -- Applied mathematics Thesis (MSc)--University of Stellenbosch, 2004. ENGLISH ABSTRACT: Motivation for the study of protection strategies for graphs is rooted in antiquity and has evolved as a subdiscipline of graph theory since the early 1990s. Using, as a point of departure, the notions of weak Roman domination and secure domination (where protection of a graph is required against a single attack) an initial framework for higher order domination was introduced in 2002 (allowing for the protection of a graph against an arbitrary finite, or even infinite, number of attacks). In this thesis, the theory of higher order domination in graphs is broadened yet further to include the possibility of an arbitrary number of guards being stationed at a vertex. The thesis firstly provides a comprehensive survey of the combinatorial literature on Roman domination, weak Roman domination, secure domination and other higher order domination strategies, with a view to summarise the state of the art in the theory of higher order graph domination as at the start of 2004. Secondly, a generalised framework for higher order domination is introduced in two parts: the first catering for the protection of a graph against a finite number of consecutive attacks, and the second concerning the perpetual security of a graph (protection of the graph against an infinite number of consecutive attacks). Two types of higher order domination are distinguished: smart domination (requiring the existence of a protection strategy for any sequence of consecutive attacks of a pre–specified length, but leaving it up to a strategist to uncover such a guard movement strategy for a particular instance of the attack sequence), and foolproof domination (requiring that any possible guard movement strategy be a successful protection strategy for the graph in question). Properties of these higher order domination parameters are examined—first by investigating the application of known higher order domination results from the literature, and secondly by obtaining new results, thereby hopefully improving current understanding of these domination parameters. Thirdly, the thesis contributes by (i) establishing higher order domination parameter values for some special graph classes not previously considered (such as complete multipartite graphs, wheels, caterpillars and spiders), by (ii) summarising parameter values for special graph classes previously established (such as those for paths, cycles and selected cartesian products), and by (iii) improving higher order domination parameter bounds previously obtained (in the case of the cartesian product of two cycles). Finally, a clear indication of unresolved problems in higher order graph domination is provided in the conclusion to this thesis, together with some suggestions as to possibly desirable future generalisations of the theory. AFRIKAANSE OPSOMMING: Die motivering vir die studie van verdedigingstrategie¨e vir grafieke het sy ontstaan in die antieke wˆereld en het sedert die vroe¨e 1990s as ’n subdissipline in grafiekteorie begin ontwikkel. Deur gebruik te maak van die idee van swak Romynse dominasie en versterkte dominasie (waar verdediging van ’n grafiek teen ’n enkele aanval vereis word) het ’n aanvangsraamwerk vir ho¨er– orde dominasie (wat ’n grafiek teen ’n veelvuldige, of selfs oneindige aantal, aanvalle verdedig) in 2002 die lig gesien. Die teorie van ho¨er–orde dominasie in grafieke word in hierdie tesis verbreed, deur toe te laat dat ’n arbitrˆere aantal wagte by elke punt van die grafiek gestasioneer mag word. Eerstens voorsien die tesis ’n omvangryke oorsig van die kombinatoriese literatuur oor Romynse dominasie, swak Romynse dominasie, versterkte dominasie en ander ho¨er–orde dominasie strategie ¨e, met die doel om die kundigheid betreffende die teorie van ho¨er–orde dominasie, soos aan die begin van 2004, op te som. Tweedens word ’n veralgemeende raamwerk vir ho¨er–orde dominasie bekendgestel, en wel in twee dele. Die eerste deel maak voorsiening vir die verdediging van ’n grafiek teen ’n eindige aantal opeenvolgende aanvalle, terwyl die tweede deel betrekking het op die oneindige sekuriteit van ’n grafiek (verdediging teen ’n oneindige aantal opeenvolgende aanvalle). Daar word tussen twee tipes h¨oer–orde dominasie onderskei: intelligente dominasie (wat slegs die bestaan van ’n verdedigingstrategie vir enige reeks opeenvolgende aanvalle vereis, maar dit aan ’n strateeg oorlaat om ’n suksesvolle bewegingstrategie vir die verdediging teen ’n spesifieke reeks aanvalle te vind), en onfeilbare dominasie (wat vereis dat enige moontlike bewegingstrategie resulteer in ’n suksesvolle verdedigingstrategie vir die betrokke grafiek). Eienskappe van hierdie ho¨er–orde dominasie parameters word ondersoek, deur eerstens die toepasbaarheid van bekende ho¨er–orde dominasie resultate vanuit die literatuur te assimileer, en tweedens nuwe resultate te bekom, in die hoop om die huidige kundigheid met betrekking tot hierdie dominasie parameters te verbreed. Derdens word ’n bydrae gelewer deur (i) ho¨er–orde dominasie parameterwaardes vas te stel vir sommige spesiale klasse grafieke wat nie voorheen ondersoek is nie (soos volledig veelledige grafieke, wiele, ruspers en spinnekoppe), deur (ii) parameterwaardes wat reeds bepaal is (soos byvoorbeeld di´e vir paaie, siklusse en sommige kartesiese produkte) op te som, en deur (iii) bekende ho¨er–orde dominasie parametergrense te verbeter (in die geval van die kartesiese produk van twee siklusse). Laastens word ’n aanduiding van oop probleme in die teorie van ho¨er–orde dominasie in die slothoofstuk van die tesis voorsien, tesame met voorstelle ten opsigte van moontlik sinvolle veralgemenings van die teorie. 2011-08-22T13:47:42Z 2011-08-22T13:47:42Z 2004-12 Thesis http://hdl.handle.net/10019.1/16257 en_ZA University of Stellenbosch xxiv, 145 leaves : ill. application/pdf Stellenbosch : University of Stellenbosch |
| spellingShingle | Domination (Graph theory) Graph theory Theses -- Applied mathematics Dissertations -- Applied mathematics Benecke, Stephen Higher order domination of graphs |
| title | Higher order domination of graphs |
| title_full | Higher order domination of graphs |
| title_fullStr | Higher order domination of graphs |
| title_full_unstemmed | Higher order domination of graphs |
| title_short | Higher order domination of graphs |
| title_sort | higher order domination of graphs |
| topic | Domination (Graph theory) Graph theory Theses -- Applied mathematics Dissertations -- Applied mathematics |
| url | http://hdl.handle.net/10019.1/16257 |
| work_keys_str_mv | AT beneckestephen higherorderdominationofgraphs |