Graph Protection and Domination

这个项目的长期目标是推动图形保护理论的发展。图是按规定方式连接的节点网络。例如，这些节点可以是岛屿，当它们之间有直接渡轮服务时，两个节点被连接起来。“保护”一词源于公元300年君士坦丁皇帝为保护罗马帝国而使用的一种军事策略。图保护涉及将资源放置在战略位置的节点上。例如，如果每个岛屿都有自己的学校是不可能的，那么我们是否可以建造学校并设计轮渡路线，使每个没有学校的岛屿与学校之间只有一次轮渡的距离？涉及的费用是什么？我的研究重点是图保护理论。将节点上的资源视为固定的监视设备，当每个位置对摄像机或运动传感器可见时，它们可以保护图形免受入侵者的侵害。作为广播单位，它们可以通过图表传播信息。在安全方面，人们可以将这些资源视为流动警卫，这一术语可以解释为军事人员、紧急服务等。想象一个节点受到入侵者攻击的紧急情况。如果一个守卫位于节点，他们可以防御它。否则，来自相邻节点的守卫必须通过链路移动到被攻击节点。每次移动后，每个节点要么有一个守卫，要么链接到一个有守卫的节点。这使得守卫能够击退反复的攻击，而无需返回到之前的位置。为了成功地进行防御，成本和效率之间存在冲突，这两者都取决于守卫的数量和他们的机动性。挑战在于平衡这些对立的因素。我的目标是用创新的想法来进一步开发最佳保护策略的模型。我的研究包括根据不同的模型确定防御的成本、效率和质量，以及优化成功防御所需的警卫数量等方面。其他重要的考虑是研究特定网络的稳定性和脆弱性，并分析允许有效战略的网络。我的目标是在解决这些领域的重大开放性问题上取得突破，并将成果发表在同行评议的期刊上。这些成果将填补现有的空白，开辟新的研究途径，为建立综合性的图保护理论做出重要贡献。这一理论可以为设施安置政策提供信息，并评估其在社会网络中的影响。在不同最优解之间的转换提供了这类解的数量及其相互关系的信息。培养和指导一个多元化的研究生团队，这是我的研究计划的一个组成部分，将有助于能力建设，以确保加拿大在未来的STEM领域保持竞争力。

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.