Why is the diameter of a random graph important?

Question

I can see the diameter of a graph, defined as the length of the longest shortest path, is a non-trivial quantity in a random graph e.g. the random graph $G(n,p)$ formed by adding edges between $n$ points independently with probability $p$.

But what makes it so mathematically significant? What relations does it have to the other fundamental graph ideas? Moreover, if I add some constraint on the graph, such as the degree distribution, or spatial constraints on the vertices (i.e. random geometric graph), what does this do to the significance of the graph diameter?

Answer 1

Graph diameter is significant in its own right, in the same way the chromatic number or maximum degree is. If you want your graph to model a network, it tells you the maximum number of 'hops' that one has to take to get from one node to any other. If your graph is embedded geometrically as, say, a graph where each edge is a straight line of length 1, then the diameter of the (abstract) graph is an upper bound on the diameter of the embedded graph, considered as a subset of $\mathbb{R}^n$.

Let $D$ be the diameter of a graph, $n$ its order, $\Delta$ its maximum degree and $\kappa$ its connectivity. Some general heuristics for how diameter behaves (these are trends, not theorems):

• If a graph has low diameter, and many vertices, then it must have many edges, and these edges must be distributed in a somewhat 'uniform' way so as not to allow any two vertices to be far apart.
• If the diameter of the graph is very large compared to the number of vertices, then the graph has fewer edges.
• In a similar vein to the above points, the diameter and maximum degree together bound the total number of vertices a graph can have. Heuristically, you can't get more vertices out of a graph than if you create a tree of depth $D$ that branches out roughly $\Delta-1$ times at each layer, with a few extra edges to close things up. Studying this bound is the topic of the degree diameter problem.
• While the diameter and maximum degree bound $n$ from above, the diameter and connectivity bound it from below. The bound looks roughly like $n \geq \kappa \cdot (D-1)$.
• The diameter also constrains the girth of the graph. In short, if the diameter is low, and the graph contains any cycle, it must contain a cycle of short length.

Finally, diameter acts as a nice complexity constraint. If you are trying to study some structure or feature in general graphs and are getting hopelessly lost, it is often useful to consider what happens in graphs of diameter 2 (especially given some other constraint or restricted graph class to go with it). Which makes it quite fortuitous that almost all graphs have diameter 2!