Spreading and Containment in Graphs

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

Expansion processes occur in essentially every real world network. Examples are the spreading of a virus within a computer network or a society, or the propagation of a rumor within a social network. If the spreading is undesired as in the case of a virus, there are natural containment strategies that rely on the protection of individual nodes of the network. Graph theory offers a suitable setting to mathematically model and investigate such spreading and containment processes. In this project we want to study the so-called -) irreversible dynamic monopolies as a simple graph theoretical spreading model and -) the firefighter game as a simple graph theoretical containment model. Our goals are structural and algorithmic results concerning these two fundamental notions and their variants.