Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Acadia University

$18,000.00

Some Further Problems in Graph Theory

EF 2022-23

Résumé
In this proposal, we consider some graph theoretic problems. In particular, we focus on three areas: graph searching (Cops and Robber), graph colouring/labelling, and graph reconfiguration which intersects with the other two areas. The research program described here has several themes. For instance, we will often be interested in studying the structural properties of the graphs under consideration. My primary objective in undertaking this research is to advance knowledge in the field of graph theory. In addition to keeping Canada at the forefront of such mathematical research, there are significant practical applications of the proposed research program. Graphs make great models. For instance, we can represent the regions of a map by vertices, with two vertices adjacent, i.e. joined by an edge, whenever the corresponding regions share a non--trivial border. When printing maps, it is desirable to minimize the number of colours needed so that regions which share a border receive different colours. In terms of the corresponding graph, we would like to minimize the number of colours, or simply labels, needed to colour the vertices in such a way that adjacent vertices receive different colours. This is the well--studied graph colouring problem. In addition to the many applications of graph colouring/labelling in scheduling and resource allocation, one application of my work in Skolem labelling is to model the configuration of communications networks with a central hub which directs information to different nodes of the network. One application of the proposed research in graph searching is network security. Computer networks are often targeted by malware. Although one layer of security is provided by firewalls & antivirus software, all that is needed for the security of the entire network to be jeopardized is for one computer to be vulnerable. My research in graph searching looks at addressing this weakness in network security by developing efficient algorithms that are designed to locate these viruses so that they can be quarantined before infecting the network. Other applications include criminal apprehension, building security, the tracking of users in cellular networks, and solving telecommunications problems related to routing. With regard to my work in reconfiguration, many problems of both practical and theoretical interest involve appropriate transitions from one configuration to another. For example, if a subset of routers in a network are monitoring packet flow, the need for maintenance will regularly make it necessary to transition from one set of routers to another. Of course, monitoring must be uninterrupted during the changeover. This problem can be modelled via the reconfiguration of vertex covers in a graph. As above, one aspect of this proposal is reconfiguration of cops/guards in a network. The proposed research program will provide training opportunities at the undergraduate, graduate, and postdoctoral levels.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Nova Scotia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2020-06528
Name nom
Clarke, Nancy
Department département
Mathematics and Statistics - Mathematics and Statistics
Organization id
78
Institution établissement
Acadia University
Province en
Nova Scotia
Province fr
Nouvelle-Écosse
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2022
Competition year année de concours
2020
Award amount
18000
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
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
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
Installment
inst:3
Partie
1
Nb partie
5
Application title
Some Further Problems in Graph Theory
Application summary
In this proposal, we consider some graph theoretic problems. In particular, we focus on three areas: graph searching (Cops and Robber), graph colouring/labelling, and graph reconfiguration which intersects with the other two areas. The research program described here has several themes. For instance, we will often be interested in studying the structural properties of the graphs under consideration. My primary objective in undertaking this research is to advance knowledge in the field of graph theory. In addition to keeping Canada at the forefront of such mathematical research, there are significant practical applications of the proposed research program. Graphs make great models. For instance, we can represent the regions of a map by vertices, with two vertices adjacent, i.e. joined by an edge, whenever the corresponding regions share a non--trivial border. When printing maps, it is desirable to minimize the number of colours needed so that regions which share a border receive different colours. In terms of the corresponding graph, we would like to minimize the number of colours, or simply labels, needed to colour the vertices in such a way that adjacent vertices receive different colours. This is the well--studied graph colouring problem. In addition to the many applications of graph colouring/labelling in scheduling and resource allocation, one application of my work in Skolem labelling is to model the configuration of communications networks with a central hub which directs information to different nodes of the network. One application of the proposed research in graph searching is network security. Computer networks are often targeted by malware. Although one layer of security is provided by firewalls & antivirus software, all that is needed for the security of the entire network to be jeopardized is for one computer to be vulnerable. My research in graph searching looks at addressing this weakness in network security by developing efficient algorithms that are designed to locate these viruses so that they can be quarantined before infecting the network. Other applications include criminal apprehension, building security, the tracking of users in cellular networks, and solving telecommunications problems related to routing. With regard to my work in reconfiguration, many problems of both practical and theoretical interest involve appropriate transitions from one configuration to another. For example, if a subset of routers in a network are monitoring packet flow, the need for maintenance will regularly make it necessary to transition from one set of routers to another. Of course, monitoring must be uninterrupted during the changeover. This problem can be modelled via the reconfiguration of vertex covers in a graph. As above, one aspect of this proposal is reconfiguration of cops/guards in a network. The proposed research program will provide training opportunities at the undergraduate, graduate, and postdoctoral levels.