Two-Connected Graphs with Given Diameter - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport Année : 2001

Two-Connected Graphs with Given Diameter

Résumé

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$).

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-4307.pdf (260.35 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00072280 , version 1 (23-05-2006)

Identifiants

  • HAL Id : inria-00072280 , version 1

Citer

Aubin Jarry, Alexandre Laugier. Two-Connected Graphs with Given Diameter. RR-4307, INRIA. 2001. ⟨inria-00072280⟩
132 Consultations
358 Téléchargements

Partager

Gmail Facebook X LinkedIn More