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

• Final Report Year: 2018

Final Report Abstract

The topic of this project were spreading processes on graphs motivated by real world phenomena or by problems coming from other theoretical areas. We studied dynamic monopolies in networks whose vertices have degree dependent susceptibilities, efficient ways to cover an entire graph by a spreading process of unit speed for which the seed vertices are chosen one by one in discrete rounds, and the formation of the convex hull within the geodetic con vexity on graphs. We contributed new insights into so-called zero forcing, which was originally motivated by matrix theory/linear algebra. Finally, inspired by deadlock prevention techniques from distributed computing, we introduced and studied generalized threshold processes on graphs.

Publications

• Extremal Values and Bounds for the Zero Forcing Number, Discrete Applied Mathematics 214 (2016) 196-200
  M. Gentner, L.D. Penso, D. Rautenbach, and U.S. Souza
  (See online at https://doi.org/10.1016/j.dam.2016.06.004)
• Dynamic Monopolies for Degree Proportional Thresholds in Connected Graphs of Girth at least Five and Trees, Theoretical Computer Science 667 (2017) 93-100
  M. Gentner and D. Rautenbach
  (See online at https://doi.org/10.1016/j.tcs.2016.12.028)
• Generalized Threshold Processes on Graphs, Theoretical Computer Science 689 (2017) 27-35
  C.V.G.C. Lima, D. Rautenbach, U.S. Souza, and J.L. Szwarcfiter
  (See online at https://doi.org/10.1016/j.tcs.2017.05.010)
• Some Bounds on the Zero Forcing Number of a Graph, Discrete Applied Mathematics 236 (2018) 203-213
  M. Gentner and D. Rautenbach
  (See online at https://doi.org/10.1016/j.dam.2017.11.015)