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.