Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648287 | Discrete Mathematics | 2012 | 6 Pages |
Abstract
We 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].
► We introduce the notion of peri-eccentricity which relates the trail decomposition of lobes to the diameter a graph. ► We give a tight minimum bound for the number of edges of a 2-connected graph with given diameter. ► We prove a tight minimum bound for the number of edges of a 2-edge-connected graph with given diameter.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
A. Jarry, A. Laugier,