TOPICS
Search

Maximally Dense Unit-Distance Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A maximally dense unit-distance graph is a unit-distance graph having the maximum possible number of edges (i.e., maximum graph density) for a given number of vertices. Finding a maximally dense unit-distance graph is equivalent to solving the Erdős unit distance problem.

Alexeev et al. (2025) determined all nonisomorphic maximally dense unit-distance graph up to 21 vertices. Their counts for n=1, 2, ... are 1, 1, 1, 1, 1, 4, 1, 3, 1, 1, 2, 1, 1, 2, 1, 1, 7, 16, 3, 1, 5, ... (OEIS A385657).

The kth maximally dense unit-distance graph on n<=21 vertices will be implemented in a future version of the Wolfram Language as GraphData[{"MaximallyDenseUnitDistance", {n, k}}].

See also

Erdős Unit Distance Problem, Graph Density, Unit-Distance Graph

Explore with Wolfram|Alpha

References

Alexeev, B.; Mixon, D. G.; and Parshall, H. "The Erdős Unit Distance Problem for Small Point Sets." 12 Feb 2025. https://arxiv.org/abs/2412.11914.Agoston, P. and Pálvőlgyi, D. "An Improved Constant Factor for the Unit Distance Problem." Studia Sci. Math. Hungarica 59, 40-57, 2022.Erdős, P. "On Sets of Distances of n Points." Amer. Math. Monthly 53, 248-250, 1946.Schade, C. "Exakte Maximale Anzahlen Gleicher Abstände." Thesis. Braunschweig, Germany: TU Braunschweig, 1993.Sloane, N. J. A. Sequences A186705 and A385657 in "The On-Line Encyclopedia of Integer Sequences."Szemerédi, S. "Erdős's Unit Distance Problem." In Open Problems in Mathematics. Switzerland, Cham: Springer, 459-477, 2016.

Cite this as:

Weisstein, Eric W. "Maximally Dense Unit-Distance Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MaximallyDenseUnit-DistanceGraph.html

Subject classifications