Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T05:43:35.101Z Has data issue: false hasContentIssue false

A Note on the Diameter of a Graph

Published online by Cambridge University Press:  20 November 2018

J. A. Bondy*
Affiliation:
Mathematical Institute, Oxford
Rights & Permissions [Opens in a new window]

Extract

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.

The distance d(x, y) between vertices x, y of a graph G is the length of the shortest path from x to y in G. The diameter δ(G) of G is the maximum distance between any pair of vertices in G. i.e. δ(G) = max max d(x, y). In this note we obtain an upper bound

x ε G y ε G

for δ(G) in terms of the numbers of vertices and edges in G. Using this bound it is then shown that for any complement-connected graph G with N vertices

where is the complement of G.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1968