Spelling suggestions: "subject:"domination (graph theory)"" "subject:"domination (raph theory)""
11 |
The queen's domination problemBurger, Alewyn Petrus 11 1900 (has links)
The queens graph Qn has the squares of then x n chessboard as its vertices; two squares
are adjacent if they are in the same row, column or diagonal. A set D of squares of
Qn is a dominating set for Qn if every square of Qn is either in D or adjacent to a
square in D. If no two squares of a set I are adjacent then I is an independent set.
Let 'J'(Qn) denote the minimum size of a dominating set of Qn and let i(Qn) denote
the minimum size of an independent dominating set of Qn. The main purpose of this
thesis is to determine new values for'!'( Qn). We begin by discussing the most important
known lower bounds for 'J'(Qn) in Chapter 2. In Chapter 3 we state the hitherto known
values of 'J'(Qn) and explain how they were determined. We briefly explain how to
obtain all non-isomorphic minimum dominating sets for Q8 (listed in Appendix A). It
is often useful to study these small dominating sets to look for patterns and possible
generalisations. In Chapter 4 we determine new values for')' ( Q69 ) , ')' ( Q77 ), ')' ( Q30 )
and i (Q45 ) by considering asymmetric and symmetric dominating sets for the case
n = 4k + 1 and in Chapter 5 we search for dominating sets for the case n = 4k + 3,
thus determining the values of 'I' ( Q19) and 'I' (Q31 ). In Chapter 6 we prove the upper
bound')' (Qn) :s; 1
8
5n + 0 (1), which is better than known bounds in the literature and
in Chapter 7 we consider dominating sets on hexagonal boards. Finally, in Chapter 8
we determine the irredundance number for the hexagonal boards H5 and H7, as well as for Q5 and Q6 / Mathematical Sciences / D.Phil. (Applied Mathematics)
|
12 |
Higher order domination of graphsBenecke, Stephen 12 1900 (has links)
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.
|
13 |
Two new combinatorial problems involving dominating sets for lottery schemesGrundlingh, Werner R. 12 1900 (has links)
Thesis (PhD (Mathematical Sciences. Applied Mathematics))--University of Stellenbosch, 2004. / Suppose a lottery scheme consists of randomly selecting an unordered winning n-subset from a universal
set of m numbers, while a player participates in the scheme by purchasing a playing set of any number of unordered n-subsets from the same universal set prior to a winning draw, and is awarded a prize if ...
|
14 |
Criticality of the lower domination parameters of graphsCoetzer, Audrey 03 1900 (has links)
Thesis (MSc (Mathematical Sciences. Applied Mathematics))--University of Stellenbosch, 2007. / In this thesis we focus on the lower domination parameters of a graph G, denoted ¼(G), for
¼ 2 {i, ir, °}. For each of these parameters, we are interested in characterizing the structure of
graphs that are critical when faced with small changes such as vertex-removal, edge-addition and
edge-removal. While criticality with respect to independence and domination have been well
documented in the literature, many open questions still remain with regards to irredundance.
In this thesis we answer some of these questions.
First we describe the relationship between transitivity and criticality. This knowledge we then
use to determine under which conditions certain classes of graphs are critical. Each of the
chosen classes of graphs will provide specific examples of different types of criticality. We also
formulate necessary conditions for graphs to be ir-critical and ir-edge-critical.
|
15 |
Two conjectures on 3-domination critical graphsMoodley, Lohini 01 1900 (has links)
For a graph G = (V (G), E (G)), a set S ~ V (G) dominates G if each vertex
in V (G) \S is adjacent to a vertex in S. The domination number I (G) (independent
domination number i (G)) of G is the minimum cardinality amongst its dominating
sets (independent dominating sets). G is k-edge-domination-critical, abbreviated k-1-
critical, if the domination number k decreases whenever an edge is added. Further, G
is hamiltonian if it has a cycle that passes through each of its vertices.
This dissertation assimilates research generated by two conjectures:
Conjecture I. Every 3-1-critical graph with minimum degree at least two is hamiltonian.
Conjecture 2. If G is k-1-critical, then I ( G) = i ( G).
The recent proof of Conjecture I is consolidated and presented accessibly. Conjecture
2 remains open for k = 3 and has been disproved for k :::>: 4. The progress is
detailed and proofs of new results are presented. / Mathematical Science / M. Sc. (Mathematics)
|
16 |
The queen's domination problemBurger, Alewyn Petrus 11 1900 (has links)
The queens graph Qn has the squares of then x n chessboard as its vertices; two squares
are adjacent if they are in the same row, column or diagonal. A set D of squares of
Qn is a dominating set for Qn if every square of Qn is either in D or adjacent to a
square in D. If no two squares of a set I are adjacent then I is an independent set.
Let 'J'(Qn) denote the minimum size of a dominating set of Qn and let i(Qn) denote
the minimum size of an independent dominating set of Qn. The main purpose of this
thesis is to determine new values for'!'( Qn). We begin by discussing the most important
known lower bounds for 'J'(Qn) in Chapter 2. In Chapter 3 we state the hitherto known
values of 'J'(Qn) and explain how they were determined. We briefly explain how to
obtain all non-isomorphic minimum dominating sets for Q8 (listed in Appendix A). It
is often useful to study these small dominating sets to look for patterns and possible
generalisations. In Chapter 4 we determine new values for')' ( Q69 ) , ')' ( Q77 ), ')' ( Q30 )
and i (Q45 ) by considering asymmetric and symmetric dominating sets for the case
n = 4k + 1 and in Chapter 5 we search for dominating sets for the case n = 4k + 3,
thus determining the values of 'I' ( Q19) and 'I' (Q31 ). In Chapter 6 we prove the upper
bound')' (Qn) :s; 1
8
5n + 0 (1), which is better than known bounds in the literature and
in Chapter 7 we consider dominating sets on hexagonal boards. Finally, in Chapter 8
we determine the irredundance number for the hexagonal boards H5 and H7, as well as for Q5 and Q6 / Mathematical Sciences / D.Phil. (Applied Mathematics)
|
17 |
Global Secure Sets Of Trees And Grid-like GraphsHo, Yiu Yu 01 January 2011 (has links)
Let G = (V, E) be a graph and let S ⊆ V be a subset of vertices. The set S is a defensive alliance if for all x ∈ S, |N[x] ∩ S| ≥ |N[x] − S|. The concept of defensive alliances was introduced in [KHH04], primarily for the modeling of nations in times of war, where allied nations are in mutual agreement to join forces if any one of them is attacked. For a vertex x in a defensive alliance, the number of neighbors of x inside the alliance, plus the vertex x, is at least the number of neighbors of x outside the alliance. In a graph model, the vertices of a graph represent nations and the edges represent country boundaries. Thus, if the nation corresponding to a vertex x is attacked by its neighbors outside the alliance, the attack can be thwarted by x with the assistance of its neighbors in the alliance. In a different subject matter, [FLG00] applies graph theory to model the world wide web, where vertices represent websites and edges represent links between websites. A web community is a subset of vertices of the web graph, such that every vertex in the community has at least as many neighbors in the set as it has outside. So, a web community C satisfies ∀x ∈ C, |N[x] ∩ C| > |N[x] − C|. These sets are very similar to defensive alliances. They are known as strong defensive alliances in the literature of alliances in graphs. Other areas of application for alliances and related topics include classification, data clustering, ecology, business and social networks. iii Consider the application of modeling nations in times of war introduced in the first paragraph. In a defensive alliance, any attack on a single member of the alliance can be successfully defended. However, as will be demonstrated in Chapter 1, a defensive alliance may not be able to properly defend itself when multiple members are under attack at the same time. The concept of secure sets is introduced in [BDH07] for exactly this purpose. The non-empty set S is a secure set if every subset X ⊆ S, with the assistance of vertices in S, can successfully defend against simultaneous attacks coming from vertices outside of S. The exact definition of simultaneous attacks and how such attacks may be defended will be provided in Chapter 1. In [BDH07], the authors presented an interesting characterization for secure sets which resembles the definition of defensive alliances. A non-empty set S is a secure set if and only if ∀X ⊆ S, |N[X] ∩ S| ≥ |N[X] − S| ([BDH07], Theorem 11). The cardinality of a minimum secure set is the security number of G, denoted s(G). A secure set S is a global secure set if it further satisfies N[S] = V . The cardinality of a minimum global secure set of G is the global security number of G, denoted γs(G). In this work, we present results on secure sets and global secure sets. In particular, we treat the computational complexity of finding the security number of a graph, present algorithms and bounds for the global security numbers of trees, and present the exact values of the global security numbers of paths, cycles and their Cartesian products.
|
18 |
Edge criticality in secure graph dominationDe Villiers, Anton Pierre 12 1900 (has links)
Thesis (PhD)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: The 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.
This graph parameter has been studied extensively since its introduction during the early 1960s
and finds application in the generic setting where the vertices of the graph denote physical
entities that are typically geographically dispersed and have to be monitored efficiently, while
the graph edges model links between these entities which enable guards, stationed at the vertices,
to monitor adjacent entities.
In the above application, the guards remain stationary at the entities. In 2005, this constraint
was, however, relaxed by the introduction of a new domination-related parameter, called the
secure domination number. In this relaxed, dynamic setting, each unoccupied entity is defended
by a guard stationed at an adjacent entity who can travel along an edge to the unoccupied entity
in order to resolve a security threat that may occur there, after which the resulting configuration
of guards at the entities is again required to be a dominating set of the graph. The secure
domination number of a graph is the smallest number of guards that can be placed on its
vertices so as to satisfy these requirements.
In this generalised setting, the notion of edge removal is important, because one might seek the
cost, in terms of the additional number of guards required, of protecting the complex of entities
modelled by the graph if a number of edges in the graph were to fail (i.e. a number of links
were to be eliminated form the complex, thereby disqualifying guards from moving along such
disabled links).
A comprehensive survey of the literature on secure graph domination is conducted in this dissertation.
Descriptions of related, generalised graph protection parameters are also given. The
classes of graphs with secure domination number 1, 2 or 3 are characterised and a result on
the number of defenders in any minimum secure dominating set of a graph without end-vertices
is presented, after which it is shown that the decision problem associated with computing the
secure domination number of an arbitrary graph is NP-complete.
Two exponential-time algorithms and a binary programming problem formulation are presented
for computing the secure domination number of an arbitrary graph, while a linear algorithm is
put forward for computing the secure domination number of an arbitrary tree. The practical
efficiencies of these algorithms are compared in the context of small graphs.
The smallest and largest increase in the secure domination number of a graph are also considered
when a fixed number of edges are removed from the graph. Two novel cost functions are
introduced for this purpose. General bounds on these two cost functions are established, and
exact values of or tighter bounds on the cost functions are determined for various infinite classes
of special graphs. Threshold information is finally established in respect of the number of possible edge removals
from a graph before increasing its secure domination number. The notions of criticality and
stability are introduced and studied in this respect, focussing on the smallest number of arbitrary
edges whose deletion necessarily increases the secure domination number of the resulting graph,
and the largest number of arbitrary edges whose deletion necessarily does not increase the secure
domination number of the resulting graph. / AFRIKAANSE OPSOMMING: Die dominasiegetal van ’n grafiek is die kardinaalgetal van ’n kleinste deelversameling van die
grafiek se puntversameling met die eienskap dat elke punt van die grafiek in die deelversameling
is of naasliggend is aan ’n punt in die deelversameling. Hierdie grafiekparameter is sedert die
vroeë 1960s uitvoerig bestudeer en vind toepassing in die generiese situasie waar die punte van
die grafiek fisiese entiteite voorstel wat tipies geografies verspreid is en doeltreffend gemonitor
moet word, terwyl die lyne van die grafiek skakels tussen hierdie entiteite voorstel waarlangs
wagte, wat by die entiteite gebaseer is, naasliggende entiteite kan monitor.
In die bogenoemde toepassing, bly die wagte bewegingloos by die fisiese entiteite waar hulle
geplaas word. In 2005 is hierdie beperking egter verslap met die daarstelling van ’n nuwe
dominasie-verwante grafiekparameter, bekend as die sekure dominasiegetal. In hierdie verslapte,
dinamiese situasie word elke punt sonder ’n wag deur ’n wag verdedig wat by ’n naasliggende
punt geplaas is en wat langs die verbindingslyn na die leë punt kan beweeg om daar ’n bedreiging
te neutraliseer, waarna die gevolglike plasing van wagte weer ’n dominasieversameling van die
grafiek moet vorm. Die sekure dominasiegetal van ’n grafiek is die kleinste getal wagte wat op
die punte van die grafiek geplaas kan word om aan hierdie vereistes te voldoen.
Die beginsel van lynverwydering speel ’n belangrike rol in hierdie veralgemeende situasie, omdat
daar gevra mag word na die koste, in terme van die addisionele getal wagte wat vereis word, om
die kompleks van entiteite wat deur die grafiek gemodelleer word, te beveilig indien ’n aantal
lynfalings in die grafiek plaasvind (m.a.w. indien ’n aantal skakels uit die kompleks van entiteite
verwyder word, en wagte dus nie meer langs sulke skakels mag beweeg nie).
’n Omvattende literatuurstudie oor sekure dominasie van grafieke word in hierdie verhandeling
gedoen. Beskrywings van verwante, veralgemeende verdedigingsparameters in grafiekteorie word
ook gegee. Die klasse van grafieke met sekure dominasiegetal 1, 2 of 3 word gekarakteriseer
en ’n resultaat oor die getal verdedigers in enige kleinste sekure dominasieversameling van ’n
grafiek sonder endpunte word daargestel, waarna daar getoon word dat die beslissingsprobleem
onderliggend aan die berekening van die sekure dominasiegetal van ’n arbitrêre grafiek NP-
volledig is.
Twee eksponensiële-tyd algoritmes en ’n binêre programmeringsformulering word vir die bepaling
van die sekure dominasiegetal van ’n arbitrêre grafiek daargestel, terwyl ’n lineêre algoritme vir
die berekening van die sekure dominasiegetal van ’n arbitrêre boom ontwerp word. Die praktiese
doeltreffendhede van hierdie algoritmes word vir klein grafieke met mekaar vergelyk. Die kleinste en groostste toename in die sekure dominasiegetal van ’n grafiek word ook oorweeg
wanneer ’n vaste getal lyne uit die grafiek verwyder word. Twee nuwe kostefunksies word vir
hierdie doel daargestel en algemene grense word op hierdie kostefunksies vir arbitrêre grafieke
bepaal, terwyl eksakte waardes van of verbeterde grense op hierdie kostefunksies vir verskeie
oneindige klasse van spesiale grafieke bereken word.
Drempelinligting word uiteindelik bepaal in terme van die moontlike getal lynverwyderings uit
’n grafiek voordat die sekure dominasiegetal daarvan toeneem. Die konsepte van kritiekheid en
stabiliteit word in hierdie konteks bestudeer, met ’n fokus op die kleinste getal arbitrêre lynfalings
wat noodwendig die sekure dominasiegetal van die gevolglike grafiek laat toeneem, of die grootste
getal arbitrêre lynfalings wat noodwendig die sekure dominasiegetal van die gevolglike grafiek
onveranderd laat.
|
Page generated in 0.1268 seconds