Radius-forcing sets in graphs

Peter Dankelmann, Vivienne Smithdorf, Henda C. Swart

Research output: Contribution to journalArticlepeer-review


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 dG(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 languageEnglish
Pages (from-to)39-49
Number of pages11
JournalAustralasian Journal of Combinatorics
Publication statusPublished - 1998
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Radius-forcing sets in graphs'. Together they form a unique fingerprint.

Cite this