Minimum size of a graph or digraph of given radius

Peter Dankelmann, Lutz Volkmann

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)


In this paper we show that a connected graph of order n, radius r and minimum degree δ has at least frac(1, 2) (δ n + frac((n - 1) (δ - 2), (δ - 1)r - 1)) edges, for n large enough, and this bound is sharp. We also present a similar result for digraphs.

Original languageEnglish
Pages (from-to)971-973
Number of pages3
JournalInformation Processing Letters
Issue number16
Publication statusPublished - 31 Jul 2009
Externally publishedYes


  • Digraph
  • Graph
  • Interconnection networks
  • Minimum degree
  • Radius
  • Size

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'Minimum size of a graph or digraph of given radius'. Together they form a unique fingerprint.

Cite this