Geodesic
Sharp Bounds on the Diameter of a Graph
Canadian mathematical bulletin, Tome 30 (1987) no. 1, pp. 72-74

Voir la notice de l'article provenant de la source Cambridge University Press

Let Dn.m , be the diameter of a connected undirected graph on n ≥2 vertices and n - 1 ≤ m ≤ s(n) edges, where s(n) = n(n — l)/2. Then Dn.s(n) = 1, and for m s(n) it is shown that The bounds on Dn.m , are sharp.
DOI : 10.4153/CMB-1987-010-0
Mots-clés : Primary 05C35, Secondary 68R10 
Smyth, W. F. Sharp Bounds on the Diameter of a Graph. Canadian mathematical bulletin, Tome 30 (1987) no. 1, pp. 72-74. doi: 10.4153/CMB-1987-010-0
@article{10_4153_CMB_1987_010_0,
     author = {Smyth, W. F.},
     title = {Sharp {Bounds} on the {Diameter} of a {Graph}},
     journal = {Canadian mathematical bulletin},
     pages = {72--74},
     year = {1987},
     volume = {30},
     number = {1},
     doi = {10.4153/CMB-1987-010-0},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-1987-010-0/}
}
TY  - JOUR
AU  - Smyth, W. F.
TI  - Sharp Bounds on the Diameter of a Graph
JO  - Canadian mathematical bulletin
PY  - 1987
SP  - 72
EP  - 74
VL  - 30
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CMB-1987-010-0/
DO  - 10.4153/CMB-1987-010-0
ID  - 10_4153_CMB_1987_010_0
ER  - 
%0 Journal Article
%A Smyth, W. F.
%T Sharp Bounds on the Diameter of a Graph
%J Canadian mathematical bulletin
%D 1987
%P 72-74
%V 30
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4153/CMB-1987-010-0/
%R 10.4153/CMB-1987-010-0
%F 10_4153_CMB_1987_010_0

[1] 1. Béla, Bollobás, diameter of random graphs, Trans. AMS 267-1 (1981) 41–52. Google Scholar

[2] 2. Chung, F.R.K. and Garey, M.R., Diameter bounds for altered graphs, J. Graph Theory 8 (1984) 511–534. Google Scholar

[3] 3. Bernard, Ghigny, Critique de l'algorithme de Smyth et Benzi, Master's thesis, Université Catholique de Lou vain (1984). Google Scholar

[4] 4. Victor, Klee and David, Larman, Diameters of random graphs, Can. J. Math. 33-3 (1981) 618–640. Google Scholar

[5] 5. Smyth, W.F., Algorithms for the reduction of matrix bandwidth and profile, J. Computational Appl. Math. 12 & 13 (1985) 551–561. Google Scholar

[6] 6. Smyth, W.F., Sparse random graphs have small diameter, Proc. 4th Hungarian Comp. Sci. Conf. (1985), to appear. Google Scholar

Cité par Sources :