A Note on the Diameter of a Graph
J. Adrian Bondy · Canadian Mathematical Bulletin · 1968
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.