Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Victoria

$15,000.00

Graph protection and domination

FY 2014-15

Summary
Graph protection and domination involves the placement of guards (or surveillance/broadcasting equipment, or emergency services, etc.) at strategic positions in a network. Positions in a network can be modelled by vertices of a graph, two vertices being adjacent if the corresponding positions in the network are, in some appropriate sense, reachable from each other. The guards deal with problems (called attacks) at vertices adjacent to their positions. Depending on the protection model the guards either remain stationary (""guards"" here could mean ""broadcast towers"" or ""smart servers on power lines"") or move across edges of the graph to defend other vertices against an attack (or an ambulance moves to deal with an emergency); every vertex of the graph must have access to a guard (etc.) in this way. There is a conflict between cost, which is proportional to the number of guards, and efficiency, 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, types of graphs that allow efficient defense strategies, and so on. It is often difficult to determine the minimum number of guards required for a particular kind of defense, so relating the protection parameters to other, more easily determined parameters, such as the number of vertices, number of edges, diameter or radius of the graph, forms part of my work. It is important to relate the parameters associated with the defense strategies to other graph parameters in order to place them within the context of well-studied concepts. My goal is to develop a comprehensive theory of these protection strategies in graphs, and to encourage other researchers to participate in the process. The training of undergraduate and graduate research students forms an integral part of my proposal.
Program
Discovery Grants Program - Individual
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
249749-2010
Name nom
Mynhardt, ChristinaKieka
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
2014
Competition year année de concours
2010
Award amount
15000
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
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
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
5
Nb partie
5
Application title
Graph protection and domination
Keyword
NSERC
Application summary
Graph protection and domination involves the placement of guards (or surveillance/broadcasting equipment, or emergency services, etc.) at strategic positions in a network. Positions in a network can be modelled by vertices of a graph, two vertices being adjacent if the corresponding positions in the network are, in some appropriate sense, reachable from each other. The guards deal with problems (called attacks) at vertices adjacent to their positions. Depending on the protection model the guards either remain stationary (""guards"" here could mean ""broadcast towers"" or ""smart servers on power lines"") or move across edges of the graph to defend other vertices against an attack (or an ambulance moves to deal with an emergency); every vertex of the graph must have access to a guard (etc.) in this way. There is a conflict between cost, which is proportional to the number of guards, and efficiency, 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, types of graphs that allow efficient defense strategies, and so on. It is often difficult to determine the minimum number of guards required for a particular kind of defense, so relating the protection parameters to other, more easily determined parameters, such as the number of vertices, number of edges, diameter or radius of the graph, forms part of my work. It is important to relate the parameters associated with the defense strategies to other graph parameters in order to place them within the context of well-studied concepts. My goal is to develop a comprehensive theory of these protection strategies in graphs, and to encourage other researchers to participate in the process. The training of undergraduate and graduate research students forms an integral part of my proposal.
University of Victoria - $15,000 Grant (2014-15) | Canada Spends