Graph Protection and Domination

图形保护和控制涉及在网络中的战略位置放置警卫（或监视或广播设备、应急服务、军事单位等）。有趣的是，它的历史根源在罗马帝国时期，当时君士坦丁皇帝设计了一种军事战略，称为纵深防御战略。他部署了机动野战军，这些部队强大到足以保卫罗马帝国的领土，阻止入侵的敌人，或者镇压叛乱。只有当野战军从至少有一支其他军队帮助发动它的地区转移过来时，野战军才被认为有能力部署到邻近地区。

Graph protection and domination involves the placement of guards (or surveillance or broadcast equipment, emergency services, military units, etc.) at strategic positions in a network. Interestingly, it has its historical roots in the time of the Roman Empire when Emperor Constantine devised a military strategy, called a defense in depth strategy. He deployed mobile field armies, units of forces powerful enough to secure the regions of the Roman Empire, to stop the intruding enemy, or to suppress insurrection. A field army was considered capable of deploying to an adjacent region only if it moved from a region where there was at least one other army to help launch it. Positions in a network are modelled by nodes of a graph, two nodes being joined by a line if the corresponding positions in the network are, in some appropriate sense, reachable from each other. The guards deal with problems, called attacks, in situ or at nodes adjacent to their positions. Depending on the model the guards either remain stationary or move across lines to repel an attack; every vertex of the graph must have access to a guard in this way. There is a conflict between cost and efficiency, both of which are proportional to the number of guards and the type of guard movements, and it is a challenge to balance the opposing forces. My research focuses on the abstract mathematical theory of these protection strategies. The theory involves aspects such as the smallest number of guards required for a successful defense, algorithms to find these numbers, the most efficient strategies, types of networks that allow efficient defense strategies, the stability and vulnerability of specific types of networks, and so on. It is often difficult to determine the minimum number of guards required for a particular kind of defense, therefore relating the protection parameters to other, more easily determined parameters, such as the number of nodes or lines, the diameter or radius of the graph, forms part of my work. This is important in order to place them within the context of well-studied concepts. Although the protection models described above arose from Constantine's military strategy, as models of modern military strategy they are oversimplified. Nevertheless, models are tools for reasoning about problems and provide ways to formalize concepts such as the effect of different defense strategies on the cost and quality of the defense, and of the destruction of links in a network on its efficiency. The ideas developed here are of interest as mathematical concepts and problems, and also have other potential applications, such as to voting strategies and the spread of diseases. My goal is to develop a comprehensive theory of these protection strategies, and to encourage other researchers to participate in the process. The training and mentoring of undergraduate and graduate research students forms an integral part of my proposal.