Abstract
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 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