TOPICS
Search

Diameter Graph


A diameter graph of a finite set S of at least two points in Euclidean space is the simple graph with vertex set S in which two distinct vertices are adjacent iff their Euclidean distance is the generalized diameter of S (Graham 1975, p. 166). The graph diameter is a different quantity defined using graph distance.

For the vertex set of a regular polygon with an odd number n>=3 of sides, the diameter graph is the cycle graph C_n. For an even number n>=4 of sides, it is the graph disjoint union of n/2 copies of the complete graph K_2, joining opposite vertices. Indeed, the longest chords advance (n-1)/2 steps around the odd polygon and n/2 steps around the even polygon.

Diameter graphs record the distance constraints attained with equality in the biggest little polygon problem, where the polygon diameter is fixed and the area is maximized.


See also

Biggest Little Polygon, Generalized Diameter, Polygon Diameter

Explore with Wolfram|Alpha

References

Foster, J. and Szabó, T. "Diameter Graphs of Polygons and the Proof of a Conjecture of Graham." J. Combin. Th. Ser. A 114, 1515-1525, 2007. https://doi.org/10.1016/j.jcta.2007.02.006.Graham, R. L. "The Largest Small Hexagon." J. Combin. Th. Ser. A 18, 165-170, 1975. https://doi.org/10.1016/0097-3165(75)90004-7.

Cite this as:

Weisstein, Eric W. "Diameter Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/DiameterGraph.html

Subject classifications