Menu
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) \leq \frac{2n}{3} \), while \( r_2(G) \leq \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) \leq \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 \).