Ingraph theory, thediameter of a connected undirected graph is the farthestdistance between any two of its vertices. That is, it is thediameter of a set for the set of vertices of the graph, and for theshortest-path distance in the graph. 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.

Thedegree diameter problem seeks tight relations between the diameter, number of vertices, anddegree of a graph. One way of formulating it is to ask for the largest graph with given bounds on its degree and diameter. For any fixed degree, this maximum size is exponential in diameter, with the base of the exponent depending on the degree.^[1]

Thegirth of a graph, the length of its shortest cycle, can be at most${\displaystyle 2k+1}$ for a graph of diameter${\displaystyle k}$. Theregular graphs for which the girth is exactly${\displaystyle 2k+1}$ are theMoore graphs. Only finitely many Moore graphs exist, but their exact number is unknown. They provide the solutions to the degree diameter problem for their degree and diameter.^[2]

Small-world networks are a class of graphs with low diameter, modeling the real-world phenomenon ofsix degrees of separation insocial networks.^[3]

The diameter of a graph can be computed by using ashortest path algorithm to compute shortest paths between all pairs of vertices, and then taking the maximum of the distances that it computes. For instance, in a graph with positive edge weights, this can be done by repeatedly usingDijkstra's algorithm, once for each possible starting vertex. In a graph with${\displaystyle n}$ vertices and${\displaystyle m}$ edges, this takes time${\displaystyle O(mn+n^2\log n)}$. 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 abreadth-first search, giving time${\displaystyle O(mn)}$. Alternatively, the diameter may be computed using an algorithm based onfast matrix multiplication, in time proportional to the time for multiplying${\displaystyle n\times n}$ matrices, approximately${\displaystyle O(n^{2.37})}$ using known matrix multiplication algorithms.^[5] For sparse graphs, with few edges, repeated breadth-first search is faster than matrix multiplication. Assuming thestrong exponential time hypothesis, repeated breadth-first search is near-optimal: this hypothesis implies that no algorithm can achieve time${\displaystyle O(n^{2-\epsilon })}$ for any${\displaystyle \epsilon >0}$.^[4]

It is possible to approximate the diameter of a weighted graph to within anapproximation ratio of 3/2, in time${\displaystyle \tilde{O}(min(m^{3/2},m{n}^{2/3})}$, where the${\displaystyle \tilde{O}}$ 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 forinterval graphs,^[7] and in near-linear time for graphs of boundedtreewidth.^[8] Inmedian graphs, the diameter can be found in the subquadratic time bound${\displaystyle \tilde{O}(n^{1.6456})}$.^[9]In any class of graphs closed undergraph minors, such as theplanar graphs, it is possible to compute the diameter in subquadratic time, with an exponent depending on the graph family.^[10]

• Triameter (graph theory)
• Diameter (group theory), the diameter of aCayley graph of the group, for generators chosen to make this diameter as large as possible
• Flip distance § Diameter of the flip graph, connecting pairs of triangulations by local moves

• Graph distance
• Graph invariants
• Computational problems in graph theory

• CS1: long volume value
• Articles with short description
• Short description is different from Wikidata
• Use mdy dates from December 2024
• Use list-defined references from December 2024