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.**