Unit distance graph
A unit distance graph is a geometric graph in which each edge is equal. Edges of a unit distance graph may overlap, ie the graph is not always planar. A unit distance graph without overlapping is called matchstick graph.
The problem of Hadwiger and Nelson deals with the chromatic number of the graph. Each unit distance graph can be colored with at most seven colors, but well known, there are also some graphs that require at least four colors. Another well-known open problem deals with the question of how high the ratio of can be edge -to-node number.
Examples
The following graphs are unit distance graph:
- Each cyclic graph
- Each grid graph
- Each hypercube graph
- The Petersen graph
- The Heawood graph
- The cartwheel W7
Strict unit distance graph
Some definitions in the literature allow for the possibility that non-adjacent node pairs may also have unit distance. For example, there is a variant of the Möbius - Kantor graph of this type
According to this definition, all attenuated generalized Petersen graphs are unit distance graph. To distinguish the two definitions, a graph in which only adjacent nodes may have a unit distance, strict unit distance graph is called.
If one removes the cartwheel W7 one spoke, one obtains a non- strict subgraphs. It is not possible, nodes, and in particular the two end points of the missing spoke to so arrange that one again obtains a strict graph.
Count of unit distances
Paul Erdős presented in 1946 the problem of how to determine a set of n points, the number of pairs of points with unit distance. Formulated graph theory: how close can be a unit distance graph?
The hypercube graph has on the number of unit distances is a lower bound proportional to n log n If the points are arranged in a square grid with carefully chosen intervals, there is an improved lower bound by Erdős of
Erdős offered a prize of $ 500, if anyone finds a similar function for the upper bound. The best known upper bound is far proportional to
This limit can be regarded as counting incidences between points and unit circles, and is closely related to the theorem of Szemerédi and Trotter for incidences between points and lines.
Generalization to higher dimensions
The definition of the unit distance graph can naturally be generalized to higher-dimensional Euclidean spaces. Each graph can be embedded as a point set in a sufficiently high dimension. Maehara and Vojtěch Rödl showed in 1990 that the necessary dimension to a graph in this way to embed by the double maximum degree of the graph is bounded.
The necessary dimension to a graph so embedded that all edges have unit distance, and the necessary dimension to a graph so embedded that all edges exactly correspond to the unit distance pairs can differ substantially: the Johnson graph with 2 n nodes can be embedded into the fourth dimension, that all its edges have unit distance, but requires n - 2 dimensions for an embedding, in which only the edges are unit distance pairs.