Radius-forcing sets in graphs

Let G be a connected graph of order p and let Ø ≠ S ⊆ V(G). Then 5 is a rad(G)-forcing set (or a radius-forcing set of G) if, for each v ∈ V(G), there exists v′ ∈ S with d_G(v,v′) ≥ rad(G). The cardinality of a smallest radius-forcing set of G is called the radius-forcing number of G and is denoted by rf(G). A graph G is called a randomly k-forcing graph for a positive integer k if every k-subset of V(G) is a radius-forcing set of G. We investigate the value of rf(G) for various graphs G, and obtain some general bounds, and we characterize graphs for which rf achieves the values of 1,2,p-1, and p, respectively. We establish the NP-completeness of the calculation of rf for arbitrary graphs, and conclude with an investigation of k-randomly forcing graphs.