Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
On the (r,s)-domination number of a graph
Thesis (PhD)--Stellenbosch University, 2014.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2014
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867614083561291776 |
|---|---|
| access_status_str | Open Access |
| author | Roux, Adriana |
| author2 | Van Vuuren, J. H. |
| author_browse | Roux, Adriana Van Vuuren, J. H. |
| author_facet | Van Vuuren, J. H. Roux, Adriana |
| author_sort | Roux, Adriana |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (PhD)--Stellenbosch University, 2014. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/86266 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:46:23.902Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2014 |
| publishDateRange | 2014 |
| publishDateSort | 2014 |
| 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/86266 On the (r,s)-domination number of a graph Roux, Adriana Van Vuuren, J. H. Stellenbosch University. Faculty of Economics and Management Sciences. Dept. of Logistics. (r,s)-domination Integer domination Dissertations -- Logistics Theses -- Logistics Facilities -- Location -- Mathematical models Logistics -- Mathematical models UCTD Thesis (PhD)--Stellenbosch University, 2014. ENGLISH ABSTRACT: The (classical) domination number of a graph is the cardinality of a smallest subset of its vertex set with the property that each vertex of the graph is in the subset or adjacent to a vertex in the subset. Since its introduction to the literature during the early 1960s, this graph parameter has been researched extensively and nds application in the generic facility location problem where a smallest number of facilities must be located on the vertices of the graph, at most one facility per vertex, so that there is at least one facility in the closed neighbourhood of each vertex of the graph. The placement constraint in the above application may be relaxed in the sense that multiple facilities may possibly be located at a vertex of the graph and the adjacency criterion may be strengthened in the sense that a graph vertex may possibly be required to be adjacent to multiple facilities. More speci cally, the number of facilities that can possibly be located at the i-th vertex of the graph may be restricted to at most ri 0 and it may be required that there should be at least si 0 facilities in the closed neighbourhood of this vertex. If the graph has n vertices, then these restriction and su ciency speci cations give rise to a pair of vectors r = [r1,....., rn] and s = [s1,....., sn]. The smallest number of facilities that can be located on the vertices of a graph satisfying these generalised placement conditions is called the hr; si-domination number of the graph. The classical domination number of a graph is therefore its hr; si-domination number in the special case where r = [1,....., 1] and s = [1,....., 1]. The exact values of the hr; si-domination number, or at least upper bounds on the hr; si- domination number, are established analytically in this dissertation for arbitrary graphs and various special graph classes in the general case, in the case where the vector s is a step function and in the balanced case where r = [r,....., r] and s = [s,....., s]. A linear algorithm is put forward for computing the hr; si-domination number of a tree, and two exponential-time (but polynomial-space) algorithms are designed for computing the hr; si- domination number of an arbitrary graph. The e ciencies of these algorithms are compared to one another and to that of an integer programming approach toward computing the hr; si- domination number of a graph. AFRIKAANSE OPSOMMING: Die (klassieke) dominasiegetal van 'n gra ek is die grootte van 'n kleinste deelversameling van die gra ek se puntversameling met die eienskap dat elke punt van die gra ek in die deelversameling is of naasliggend is aan 'n punt in die deelversameling. Sedert die verskyning van hierdie gra ekparameter in the literatuur gedurende die vroeë 1960s, is dit deeglik nagevors en vind dit neerslag in die generiese plasingstoepassing waar 'n kleinste getal fasiliteite op die punte van die gra ek geplaas moet word, hoogstens een fasiliteit per punt, sodat daar minstens een fasiliteit in die geslote buurpuntversameling van elke punt van die gra ek is. Die plasingsbeperking in die bogenoemde toepassing mag egter verslap word in die sin dat meer as een fasiliteit potensieel op 'n punt van die gra ek geplaas kan word en verder mag die naasliggendheidsvereiste verhoog word in die sin dat 'n punt van die gra ek moontlik aan veelvuldige fasiliteite naasliggend moet wees. Gestel dat die getal fasiliteite wat op die i-de punt van die gra ek geplaas mag word, beperk word tot hoogstens ri 0 en dat hierdie punt minstens si 0 fasiliteite in die geslote buurpuntversameling daarvan moet hê. Indien die gra ek n punte bevat, gee hierdie plasingsbeperkings en -vereistes aanleiding tot die paar vektore r = [r1, .... , rn] en s = [s1,...., sn]. Die kleinste getal fasiliteite wat op die punte van 'n gra ek geplaas kan word om aan hierdie veralgemeende voorwaardes te voldoen, word die hr; si-dominasiegetal van die gra ek genoem. Die klassieke dominasiegetal van 'n gra ek is dus die hr; si-dominasiegetal daarvan in die spesiale geval waar r = [1,......, 1] en s = [1,....., 1]. In hierdie verhandeling word die eksakte waardes van, of minstens grense op, die hr; si-dominasiegetal van arbitrêre gra eke of spesiale klasse gra eke analities bepaal vir die algemene geval, vir die geval waar s 'n trapfunksie is, en vir die gebalanseerde geval waar r = [r,....., r] en s = [s,....., s]. 'n Lineêre algoritme word ook daargestel vir die berekening van die hr; si-dominasiegetal van 'n boom, en twee eksponensiële-tyd (maar polinoom-ruimte) algoritmes word ontwerp vir die berekening van die hr; si-dominasiegetal van 'n arbitrêre gra ek. Die doeltre endhede van hierdie algoritmes word met mekaar vergelyk en ook met dié van 'n heeltallige programmeringsbenadering tot die bepaling van die hr; si-dominasiegetal van 'n gra ek. Doctoral 2014-04-16T17:28:30Z 2014-04-16T17:28:30Z 2014-04 Thesis http://hdl.handle.net/10019.1/86266 en_ZA Stellenbosch University 143 p. application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | (r,s)-domination Integer domination Dissertations -- Logistics Theses -- Logistics Facilities -- Location -- Mathematical models Logistics -- Mathematical models UCTD Roux, Adriana On the (r,s)-domination number of a graph |
| title | On the (r,s)-domination number of a graph |
| title_full | On the (r,s)-domination number of a graph |
| title_fullStr | On the (r,s)-domination number of a graph |
| title_full_unstemmed | On the (r,s)-domination number of a graph |
| title_short | On the (r,s)-domination number of a graph |
| title_sort | on the r s domination number of a graph |
| topic | (r,s)-domination Integer domination Dissertations -- Logistics Theses -- Logistics Facilities -- Location -- Mathematical models Logistics -- Mathematical models UCTD |
| url | http://hdl.handle.net/10019.1/86266 |
| work_keys_str_mv | AT rouxadriana onthersdominationnumberofagraph |