Spreading and Containment in Graphs

• Applicant: Professor Dr. Dieter Rautenbach
• Subject Area: Mathematics
• Term: from 2014 to 2017
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 269574128

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.

• DFG Programme: Research Grants