Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Victoria

$14,000.00

Graph Protection and Domination

EF 2018-19

Résumé
Graph protection and domination involves the placement of guards (or surveillance or broadcast equipment, emergency services, military units, etc.) at strategic positions in a network. Interestingly, it has its historical roots in the time of the Roman Empire when Emperor Constantine devised a military strategy, called a defense in depth strategy. He deployed mobile field armies, units of forces powerful enough to secure the regions of the Roman Empire, to stop the intruding enemy, or to suppress insurrection. A field army was considered capable of deploying to an adjacent region only if it moved from a region where there was at least one other army to help launch it.*Positions in a network are modelled by nodes of a graph, two nodes being joined by a line if the corresponding positions in the network are, in some appropriate sense, reachable from each other. The guards deal with problems, called attacks, in situ or at nodes adjacent to their positions. Depending on the model the guards either remain stationary or move across lines to repel an attack; every vertex of the graph must have access to a guard in this way. There is a conflict between cost and efficiency, both of which are proportional to the number of guards and the type of guard movements, and it is a challenge to balance the opposing forces.*My research focuses on the abstract mathematical theory of these protection strategies. The theory involves aspects such as the smallest number of guards required for a successful defense, algorithms to find these numbers, the most efficient strategies, types of networks that allow efficient defense strategies, the stability and vulnerability of specific types of networks, and so on. It is often difficult to determine the minimum number of guards required for a particular kind of defense, therefore relating the protection parameters to other, more easily determined parameters, such as the number of nodes or lines, the diameter or radius of the graph, forms part of my work. This is important in order to place them within the context of well-studied concepts.*Although the protection models described above arose from Constantine's military strategy, as models of modern military strategy they are oversimplified. Nevertheless, models are tools for reasoning about problems and provide ways to formalize concepts such as the effect of different defense strategies on the cost and quality of the defense, and of the destruction of links in a network on its efficiency. The ideas developed here are of interest as mathematical concepts and problems, and also have other potential applications, such as to voting strategies and the spread of diseases.*My goal is to develop a comprehensive theory of these protection strategies, and to encourage other researchers to participate in the process. The training and mentoring of undergraduate and graduate research students forms an integral part of my proposal.*
Programme
Discovery Grants Program - Individual
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2015-05442
Name nom
Mynhardt, Christina
Department département
Mathematics and Statistics
Organization id
7
Institution établissement
University of Victoria
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2018
Competition year année de concours
2015
Award amount
14000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Partie
4
Nb partie
5
Application title
Graph Protection and Domination
Keyword
NSERC
Application summary
Graph protection and domination involves the placement of guards (or surveillance or broadcast equipment, emergency services, military units, etc.) at strategic positions in a network. Interestingly, it has its historical roots in the time of the Roman Empire when Emperor Constantine devised a military strategy, called a defense in depth strategy. He deployed mobile field armies, units of forces powerful enough to secure the regions of the Roman Empire, to stop the intruding enemy, or to suppress insurrection. A field army was considered capable of deploying to an adjacent region only if it moved from a region where there was at least one other army to help launch it.*Positions in a network are modelled by nodes of a graph, two nodes being joined by a line if the corresponding positions in the network are, in some appropriate sense, reachable from each other. The guards deal with problems, called attacks, in situ or at nodes adjacent to their positions. Depending on the model the guards either remain stationary or move across lines to repel an attack; every vertex of the graph must have access to a guard in this way. There is a conflict between cost and efficiency, both of which are proportional to the number of guards and the type of guard movements, and it is a challenge to balance the opposing forces.*My research focuses on the abstract mathematical theory of these protection strategies. The theory involves aspects such as the smallest number of guards required for a successful defense, algorithms to find these numbers, the most efficient strategies, types of networks that allow efficient defense strategies, the stability and vulnerability of specific types of networks, and so on. It is often difficult to determine the minimum number of guards required for a particular kind of defense, therefore relating the protection parameters to other, more easily determined parameters, such as the number of nodes or lines, the diameter or radius of the graph, forms part of my work. This is important in order to place them within the context of well-studied concepts.*Although the protection models described above arose from Constantine's military strategy, as models of modern military strategy they are oversimplified. Nevertheless, models are tools for reasoning about problems and provide ways to formalize concepts such as the effect of different defense strategies on the cost and quality of the defense, and of the destruction of links in a network on its efficiency. The ideas developed here are of interest as mathematical concepts and problems, and also have other potential applications, such as to voting strategies and the spread of diseases.*My goal is to develop a comprehensive theory of these protection strategies, and to encourage other researchers to participate in the process. The training and mentoring of undergraduate and graduate research students forms an integral part of my proposal.*