In mathematics, and particularly in graph theory, the dimension of a graph is the least integer n such that there exists a "classical representation" of the graph in the Euclidean space of dimension n with all the edges having unit length.
The dimension of the Petersen graph is 2.
In a classical representation, the vertices must be distinct points, but the edges may cross one another.[1]
The dimension of a graph G is written: dim G {\displaystyle \dim G} {\displaystyle \dim G}.
For example, the Petersen graph can be drawn with unit edges in E 2 {\displaystyle E^{2}} E^{2}, but not in \( E^{1} \): its dimension is therefore 2 (see the figure to the right).
This concept was introduced in 1965 by Paul Erdős, Frank Harary and William Tutte.[2] It generalises the concept of unit distance graph to more than 2 dimensions.
Examples
With 4 equally spaced points, we need 3 dimensions.
Complete graph
In the worst case, every pair of vertices is connected, giving a complete graph.
To immerse the complete graph \( K_{n} \) with all the edges having unit length, we need the Euclidean space of dimension n-1.[3] For example, it takes two dimensions to immerse \( K_{3} \) (an equilateral triangle), and three to immerse \( K_{4} \) (a regular tetrahedron) as shown to the right.
\( \dim K_{n}=n-1 \)
In other words, the dimension of the complete graph is the same as that of the simplex having the same number of vertices.
The complete bipartite graph \( K_{{4,2}} \)drawn in Euclidean 3-space.
Complete bipartite graphs
A star graph drawn in the plane with edges of unit length.
All star graphs \( K_{{m,1}} \), for \( m\geq 3 \), have dimension 2, as shown in the figure to the left. Star graphs with m equal to 1 or 2 need only dimension 1.
The dimension of a complete bipartite graph \( K_{{m,2}} \) , for \( m\geq 3 \), can be drawn as in the figure to the right, by placing m vertices on a circle whose radius is less than a unit, and the other two vertices one each side of the plane of the circle, at a suitable distance from it. \( K_{2,2} \) has dimension 2, as it can be drawn as a unit rhombus in the plane.
Theorem — The dimension of a general complete bipartite graph \( K_{m,n} \), for \( m\geq 3 \) and \( n\geq 3 \), is 4.
Proof
To summarise:
\( {\displaystyle \dim K_{m,n}=1,2,3{\text{ or }}4} \), depending on the values of m and n.
Dimension and chromatic number
Theorem — The dimension of any graph G is always less than or equal to twice its chromatic number:
\( {\displaystyle \dim G\leq 2\,\chi (G)} \)
Proof
Euclidean dimension
The wheel graph with one spoke removed is of dimension 2.
The same wheel is of Euclidean dimension 3.
The definition of the dimension of a graph given above says, of the minimal-n representation:
if two vertices of G are connected by an edge, they must be at unit distance apart;
however, two vertices at unit distance apart are not necessarily connected by an edge.
This definition is rejected by some authors. A different definition was proposed in 1991 by Alexander Soifer, for what he termed the Euclidean dimension of a graph.[4] Previously, in 1980, Paul Erdős and Miklós Simonovits had already proposed it with the name faithful dimension.[5] By this definition, the minimal-n representation is one such that two vertices of the graph are connected if and only if their representations are at distance 1.
The figures opposite show the difference between these definitions, in the case of a wheel graph having a central vertex and six peripheral vertices, with one spoke removed. Its representation in the plane allows two vertices at distance 1, but they are not connected.
We write this dimension as \({\displaystyle \operatorname {Edim} G} \). It is never less than the dimension defined as above:
\( {\displaystyle \dim G\leq \operatorname {Edim} G} \)
Euclidean dimension and maximal degree
Paul Erdős and Miklós Simonovits proved the following result in 1980:[5]
Theorem — The Euclidean dimension of a graph G is no more than twice its maximal degree plus one:
\( {\displaystyle \operatorname {Edim} G\leq 2\,\Delta (G)+1} \)
Computational complexity
It is NP-hard, and more specifically complete for the existential theory of the reals, to test whether the dimension or the Euclidean dimension of a given graph is at most a given value. The problem remains hard even for testing whether the dimension or Euclidean dimension is two.[6]
References
Some mathematicians regard this strictly as an "immersion", but many graph theorists, including Erdős, Harary and Tutte, use the term "embedding".
Erdős, P.; Harary, F.; Tutte, W. T. (1965). "On the dimension of a graph" (PDF). Mathematika. 12 (2): 118–122. doi:10.1112/s0025579300005222.
Kavangh, Ryan. "Explorations on the dimensionality of graphs" (PDF). Retrieved August 16, 2018.
Soifer, Alexander (2009). The Mathematical Coloring Book. Springer. ISBN 978-0-387-74640-1.
Erdős, P.; Simonovits, M. (1980). "On the chromatic number of geometric graphs". Ars Comb. (9): 229–246.
Schaefer, Marcus (2013), "Realizability of graphs and linkages", in Pach, János (ed.), Thirty Essays on Geometric Graph Theory, Springer, pp. 461–482, CiteSeerX 10.1.1.220.9651, doi:10.1007/978-1-4614-0110-0_24, ISBN 978-1-4614-0109-4.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
