On the minimum number of edges of two-connected graphs with given diameter

AbstractWe answer the following question: what is the minimum number of edges of a 2-connected graph with a given diameter? This problem stems from survivable telecommunication network design with grade-of-service constraints. In this paper, we prove tight bounds for 2-connected graphs and for 2-edge-connected graphs. The bound for 2-connected graphs was a conjecture of B. Bollobás (AMH 75–80) [3]