Graph Protection and Domination

点击翻译按钮获取中文摘要

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.