### Abstract

Let f_{d}(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 > n_{0} (D) vertices, f_{2}(G) = n - D - 1 and f_{3}(G) ≥ n - O(D^{3}). For d ≥ 4, f_{d}(G) depends strongly on the actual structure of G, not only on the maximum degree of G. We prove that the maximum of f_{d} (G) over all connected graphs on n vertices is n/[d/2] - O(1). As a byproduct, we show that for the n-cycle C_{n}, f_{d}(C_{n}) = n/ (2[d/2] - 1) - O(1) for every d and n, improving earlier estimates of Chung and Garey in certain ranges.

Original language | English (US) |
---|---|

Pages (from-to) | 161-172 |

Number of pages | 12 |

Journal | Journal of Graph Theory |

Volume | 35 |

Issue number | 3 |

DOIs | |

State | Published - Nov 2000 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Geometry and Topology

### Keywords

- Diameter of graphs
- Graphs
- Maximum degree

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

## Cite this

Alon, N., Gyárfás, A., & Ruszinkó, M. (2000). Decreasing the diameter of bounded degree graphs.

*Journal of Graph Theory*,*35*(3), 161-172. https://doi.org/10.1002/1097-0118(200011)35:3<161::AID-JGT1>3.0.CO;2-Y