## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 39-49 |

Number of pages | 11 |

Journal | Australasian Journal of Combinatorics |

Volume | 17 |

Publication status | Published - 1998 |

Externally published | Yes |

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics