Emergency Response Sets in Graphs

Abstract

We introduce a $k$-response set as a set of vertices where responders can be placed so that given any set of $k$ emergencies, these responders can respond, one per emergency, where each responder covers its own vertex and its neighbors. A weak $k$-response set does not have to worry about emergencies at the vertices of the set. We define $R_k$ and $r_k$ as the minimum cardinality of such sets. We provide bounds on these parameters and discuss connections with domination invariants. For example, for a graph $G$ of order $n$ and minimum degree at least $2$, $R_2(G)\le \frac{2n}{3}$, while $r_2(G)\le \frac{n}{2}$ provided $G$ is also connected and not $K_3$. We also provide bounds for trees $T$ of order $n$. We observe that there are, for each $k$, trees for which $r_k(T)\le \frac{n}{2}$, but that the minimum $R_k(T)$ appears to grow with $k$; a novel computer algorithm is used to show that $R_3(T)>\frac{n}{2}$. As expected, these parameters are NP-hard to compute, and we provide a linear-time algorithm for trees for fixed $k$.