Diameter (graph theory)

Diameter may be considered either for weighted or for unweighted graphs.

Researchers have studied the problem of computing the diameter, both in arbitrary graphs and in special classes of graphs.

The diameter of a disconnected graph may be defined to be infinite, or undefined.

The degree diameter problem seeks tight relations between the diameter, number of vertices, and degree of a graph.

One way of formulating it is to ask for the largest graph with given bounds on its degree and diameter.

[1] The girth of a graph, the length of its shortest cycle, can be at most

Only finitely many Moore graphs exist, but their exact number is unknown.

[2] Small-world networks are a class of graphs with low diameter, modeling the real-world phenomenon of six degrees of separation in social networks.

For instance, in a graph with positive edge weights, this can be done by repeatedly using Dijkstra's algorithm, once for each possible starting vertex.

Computing all-pairs shortest paths is the fastest known method for computing the diameter of a weighted graph exactly.

[4] In an unweighted-graph, Dijkstra's algorithm may be replaced by breadth-first search, giving time

Alternatively, the diameter may be computed using an algorithm based on fast matrix multiplication, in time proportional to the time for multiplying

[5] For sparse graphs, with few edges, repeated breadth-first search is faster than matrix multiplication.

Assuming the exponential time hypothesis, repeated breadth-first search is near-optimal: this hypothesis implies that no algorithm can achieve time

notation hides logarithmic factors in the time bound.

[6] Under the exponential time hypothesis, no substantially more accurate approximation, substantially faster than all pairs shortest paths, is possible.

[4] The diameter can be computed in linear time for interval graphs,[7] and in near-linear time for graphs of bounded treewidth.

[8] In median graphs, the diameter can be found in the subquadratic time bound