Some resources for Level 4 students on games on graphs:

Lately I’ve been spending some of my more algorithmic time on temporal and multilayer graphs and algorithms for them (e.g. https://arxiv.org/pdf/1805.06836.pdf, https://arxiv.org/abs/1802.05905) and on pursuit or spreading games for graphs.

Pursuit and spreading games are games like:
- firefighter, where a fire starts somewhere on the graph and at each turn we get some budget to defend a number of vertices. We can ask algorithmic questions like: how many vertices can we save? Can we contain things in finite time on an infinite graph? This last week I’ve been thinking about a version in which the defence also spreads, like an infectious vaccine or a competing disease. A somewhat old survey here: https://ajc.maths.uq.edu.au/pdf/43/ajc_v43_p057.pdf and a recent paper of mine with a grad student here: https://arxiv.org/abs/2202.12599
- cops and robbers, where some number of cops chase some number of robbers around a graph. There are a million variants with stealthy robbers or cops that cannot visit some vertices, etc. Here’s a blog post with some links: https://anthonybonato.com/2018/04/04/a-new-prehistory-of-cops-and-robbers/
- graph burning, where we are trying to burn a graph as fast as possible by setting fires that spread on each turn. Here’s a fairly recent survey: https://arxiv.org/abs/2009.10642
- localisation, where probes (or cops, if we want to be analogous with cops and robbers) try to find a hidden agent by getting a distance vector from a selected set of probe locations. Here’s a related paper: https://arxiv.org/abs/2105.09806, and a research seminar: https://www.youtube.com/watch?v=5cDLI-g5Y4s
- I've also thought a bit about a static version where the probe location is fixed at the start of the game, some old and draft notes on preliminary work here: https://drive.google.com/file/d/1nvS1jPLinyMFp3Xx3aVDMhQD7wh8zAw7/view?usp=sharing

And some notes from a summer school I just did on temporal graph firefighter:
https://hackmd.io/@magicicada/ss_gsac_2022