Skip to Main content Skip to Navigation

Two-Connected Graphs with Given Diameter

Aubin Jarry 1 Alexandre Laugier
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : The problem we study in this work is an extremal problem arising from graph theory : what is the minimum number of edges of a 2-connected graph satisfying diameter conditions. This problem deals with survivable netowrk design when the network is subjected to satisfy grade of service constraints. One way to provide networks working when some failures arise is to provide a sufficient connectivity to the networks. Due to equipment robustness 2-connectivity or 2-edge-connectivity will be sufficient. Notice that k-connected networks, k$\geq$3, will provide too expensive networks. Another important parameter is the crossing-delay, ie the total amount of time spent in the network by some data packet to reach its destination from its origin. In order to keep this crossing-delay under reasonable values one can bound the number of hops of a routing path. This leads to bound the diameter of the underlying graph. We prove the following bounds : if $G$ is 2-(vertex)-connected, then $|E|\geq\lceil\fracnD-(2D+1){D-1}\rceil$, if $G$ is 2-edge-connected of odd diameter, then $|E|\geq\lceil\fracnD-(2D+1){- D-1}\rceil$, if $G$ is 2-edge-connected of even diameter, then $|E|\geq min(\lceil\fracnD-(2D+1){D-1}\rceil,\lceil\frac{(n-1)(D+1)}{D}\rceil$).
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 8:17:43 PM
Last modification on : Wednesday, October 14, 2020 - 4:24:00 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:07:29 PM


  • HAL Id : inria-00072280, version 1



Aubin Jarry, Alexandre Laugier. Two-Connected Graphs with Given Diameter. RR-4307, INRIA. 2001. ⟨inria-00072280⟩



Record views


Files downloads