Article contents
A Note on the Diameter of a Graph
Published online by Cambridge University Press: 20 November 2018
Extract
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.
- Type
- Research Article
- Information
- Copyright
- Copyright © Canadian Mathematical Society 1968
References
- 3
- Cited by