Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 151.33204
Autor: Erdös, Pál; Harary, Frank; Tutte, W.T.
Title: On the dimension of a graph (In English)
Source: Mathematika, London 12, 118-122 (1965).
Review: The following concept of the dimension of a graph is presented: The dimension G of a graph G is the minimum number n such that G can be embedded into Euclidean n-space En with every edge of G having length 1. Some of the results: For the complete graph Km with m vertices dim Km = m-1; for the complete bicoloured graph Km,n, dim Km,n \leq 4, for n-dimensional cube Qn, n > 1, is dim Qn = 2 for all n. For any graph G with chromatic number \chi(G), dim G \leq 2 · \chi(G).
If dim G = 2, then \chi(G) \leq 7. Among all graphs with n vertices, q edges, and dimension 2k or 2k+1, limn ––> oo max qn-2 = 1/2 (1-k-1). Among any n points of E4 the distance 1 between pairs of points can occur at most n+[n2/4] times, and this number can be realized if n \equiv 0 (mod 8).
Reviewer: E.Jucovic
Classif.: * 05C35 Extremal problems (graph theory)
05C15 Chromatic theory of graphs and maps
05C10 Topological graph theory
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag