Decreasing the diameter of bounded degree graphs

Noga Alon, András Gyárfás, Miklós Ruszinkó

Research output: Contribution to journalArticlepeer-review

42 Scopus citations


Let fd(G) denote the minimum number of edges that have to be added to a graph G to transform it into a graph of diameter at most d. We prove that for any graph G with maximum degree D and n > n0 (D) vertices, f2(G) = n - D - 1 and f3(G) ≥ n - O(D3). For d ≥ 4, fd(G) depends strongly on the actual structure of G, not only on the maximum degree of G. We prove that the maximum of fd (G) over all connected graphs on n vertices is n/[d/2] - O(1). As a byproduct, we show that for the n-cycle Cn, fd(Cn) = n/ (2[d/2] - 1) - O(1) for every d and n, improving earlier estimates of Chung and Garey in certain ranges.

Original languageEnglish (US)
Pages (from-to)161-172
Number of pages12
JournalJournal of Graph Theory
Issue number3
StatePublished - Nov 2000
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology


  • Diameter of graphs
  • Graphs
  • Maximum degree


Dive into the research topics of 'Decreasing the diameter of bounded degree graphs'. Together they form a unique fingerprint.

Cite this