Ausbreitungs- und Eindämmungsprozesse auf Graphen

• Antragsteller: Professor Dr. Dieter Rautenbach
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2014 bis 2017
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 269574128

• Erstellungsjahr: 2018

Zusammenfassung der Projektergebnisse

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.

Projektbezogene Publikationen (Auswahl)

• 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
  (Siehe online unter 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
  (Siehe online unter 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
  (Siehe online unter 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
  (Siehe online unter https://doi.org/10.1016/j.dam.2017.11.015)