Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Victoria

$48,000.00

Graph Protection and Domination

EF 2024-25

Résumé
The long term goal of this program is to fuel advances in the theory of graph protection. A graph is a network of nodes linked in a prescribed way. These nodes could be islands, for example, with two nodes being linked when there is a direct ferry service between them. The term protection arises from a military strategy used by Emperor Constantine in ca. 300 AD to protect the Roman Empire. Graph protection involves the placement of resources at strategically located nodes. If it is impossible, for example, that every island has its own school, can we build schools and design ferry routes so that each island without a school is only a single ferry ride away from one? What are the costs involved? My research focuses on the theory of graph protection. Viewing the resources at nodes as stationary surveillance equipment, they can safeguard a graph against intruders when each location is visible to (say) a camera or motion sensor. Viewed as broadcasting units, they can spread information through the graph. In terms of security, one may instead view the resources as mobile guards, a term that may be interpreted as military personnel, emergency services, etc. Imagine an emergency situation where a node is attacked by an intruder. If a guard is located at the node, they can defend it. Otherwise, a guard from an adjacent node must move across a link to the attacked node. After each move, each node must either have a guard or be linked to a node with a guard. This enables guards to repel repeated attacks without returning to their previous positions. To mount a successful defence, there is a conflict between cost and efficiency, both depending on the number of guards and their mobility. The challenge is to balance these opposing factors. I aim to use innovative ideas to further develop models for optimal protection strategies. My research involves aspects such as determining the cost, efficiency and quality of the defence according to different models, and optimising the number of guards required for a successful defence. Other important considerations are studying the stability and vulnerability of particular networks, and analysing networks that permit efficient strategies. I aim to make breakthroughs in solving major open problems in these areas, and to publish the results in peer reviewed journals. Such results will make important contributions to building a comprehensive theory of graph protection by filling existing gaps and opening new avenues of investigation. This theory can inform facilities placement policies and assess influence in social networks. Transitioning between different optimal solutions provides information on both the number of such solutions and their relationship to one another. The training and mentoring of a diverse team of research students, which forms an integral component of my research program, will facilitate capacity building to ensure that Canada remains competitive in STEM fields in the future.
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-2020-03930
Name nom
Mynhardt, Christina
Department département
Mathematics and Statistics - 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
2024
Competition year année de concours
2020
Award amount
48000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR 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
2900
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Pure mathematics
Research subject fr
Mathématiques pures
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Graph Protection and Domination
Keywords
graph protection; eternal domination; secure domination; graph reconfiguration; broadcasts in graphs; irredundance in graphs; roman domination; broadcast independence
Application summary
The long term goal of this program is to fuel advances in the theory of graph protection. A graph is a network of nodes linked in a prescribed way. These nodes could be islands, for example, with two nodes being linked when there is a direct ferry service between them. The term protection arises from a military strategy used by Emperor Constantine in ca. 300 AD to protect the Roman Empire. Graph protection involves the placement of resources at strategically located nodes. If it is impossible, for example, that every island has its own school, can we build schools and design ferry routes so that each island without a school is only a single ferry ride away from one? What are the costs involved? My research focuses on the theory of graph protection. Viewing the resources at nodes as stationary surveillance equipment, they can safeguard a graph against intruders when each location is visible to (say) a camera or motion sensor. Viewed as broadcasting units, they can spread information through the graph. In terms of security, one may instead view the resources as mobile guards, a term that may be interpreted as military personnel, emergency services, etc. Imagine an emergency situation where a node is attacked by an intruder. If a guard is located at the node, they can defend it. Otherwise, a guard from an adjacent node must move across a link to the attacked node. After each move, each node must either have a guard or be linked to a node with a guard. This enables guards to repel repeated attacks without returning to their previous positions. To mount a successful defence, there is a conflict between cost and efficiency, both depending on the number of guards and their mobility. The challenge is to balance these opposing factors. I aim to use innovative ideas to further develop models for optimal protection strategies. My research involves aspects such as determining the cost, efficiency and quality of the defence according to different models, and optimising the number of guards required for a successful defence. Other important considerations are studying the stability and vulnerability of particular networks, and analysing networks that permit efficient strategies. I aim to make breakthroughs in solving major open problems in these areas, and to publish the results in peer reviewed journals. Such results will make important contributions to building a comprehensive theory of graph protection by filling existing gaps and opening new avenues of investigation. This theory can inform facilities placement policies and assess influence in social networks. Transitioning between different optimal solutions provides information on both the number of such solutions and their relationship to one another. The training and mentoring of a diverse team of research students, which forms an integral component of my research program, will facilitate capacity building to ensure that Canada remains competitive in STEM fields in the future.