The Diameter of Almost All Bipartite Graphs.
Victor L. Klee, Larman,D G, Wright,E M · Defense Technical Information Center (DTIC) · 1980
The diameter of a graph is of intrinsic interest as one of the most basic and most thoroughly studied parameters of graph theory. It may also be of practical concern because of the close relationship of diameters to the computational complexity of graph-theoretic algorithms based on breadth-first search. Here we consider bipartite graphs on n labelled points in one part and m=m(n) n labelled points in the other. Of the 2mn such graphs, some are disconnected and the others have diameters ranging from 2m down to 2. (Author)