English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study zombies and survivor, a variant of the game of cops and robber ongraphs. In this variant, the single survivor plays the role of the robber andattempts to escape from the zombies that play the role of the cops. The zombiesare restricted, on their turn, to always follow an edge of a shortest pathtowards the survivor. Let $z(G)$ be the smallest number of zombies required tocatch the survivor on a graph $G$ with $n$ vertices. We show that there existouterplanar graphs and visibility graphs of simple polygons such that $z(G) =\Theta(n)$. We also show that there exist maximum-degree-$3$ outerplanar graphssuch that $z(G) = \Omega\left(n/\log(n)\right)$.  Let $z_L(G)$ be the smallest number of lazy zombies (zombies that can staystill on their turn) required to catch the survivor on a graph $G$. Weestablish that lazy zombies are more powerful than normal zombies but lesspowerful than cops. We prove that $z_L(G) = 2$ for connected outerplanargraphs. We show that $z_L(G)\leq k$ for connected graphs with treedepth $k$.This result implies that $z_L(G)$ is at most $(k+1)\log n$ for connected graphswith treewidth $k$, $O(\sqrt{n})$ for connected planar graphs, $O(\sqrt{gn})$for connected graphs with genus $g$ and $O(h\sqrt{hn})$ for connected graphswith any excluded $h$-vertex minor. Our results on lazy zombies still hold whenan adversary chooses the initial positions of the zombies.

Pursuit-Evasion in Graphs: Zombies, Lazy Zombies and a Survivor