Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-15T17:25:32.335Z Has data issue: false hasContentIssue false

Sharp Bounds on the Diameter of a Graph

Published online by Cambridge University Press:  20 November 2018

W. F. Smyth*
Affiliation:
Department of Computer Science & Systems Mcmaster University Hamilton, Ontario, Canada, L8S 4K1
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 01