On the (r,s)-domination number of a graph
Date
2014-04
Authors
Roux, Adriana
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
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.
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.
Description
Thesis (PhD)--Stellenbosch University, 2014.
Keywords
(r,s)-domination, Integer domination, Dissertations -- Logistics, Theses -- Logistics, Facilities -- Location -- Mathematical models, Logistics -- Mathematical models, UCTD