Emergency Response Sets in Graphs

Jean Blair1, Wayne Goddard2, Sandra M.Hedetniemi2, Stephen T.Hedetniemi2, Fredrik Manne3, Douglas Rall4
1Dept of Computer Science, US Military Academy West Point, NY 10996, USA
2 School of Computing, Clemson University Clemson SC 29634, USA
3Dept of Informatics, University of Bergen N-5020 Bergen, Norway
4Dept of Mathematics, Furman University Greenville SC 29613, USA

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) \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 \).