1965/12/01 by P. Erdös, Frank Harary, W. T. Tutte · 5 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Citation #Combinatorics #Computer science #Dimension (graph theory) #Graph #Graph Labeling and Dimension Problems #Graph theory and applications #Library science #Mathematics
paper · doi:10.1112/s0025579300005222
openalex publication_date 1965/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15
Our purpose in this note is to present a natural geometrical definition of the dimension of a graph and to explore some of its ramifications. In 1 we determine the dimension of some special graphs. We observe in 92 that several results in the literature are unified by the concept of the dimension of a graph, and state some related unsolved problems. We define the dimension of a graph G, denoted dim G, as the minimum number n such that G can be embedded into Euclidean n-space E,, with every edge of G having length 1. The vertices of C are mapped onto distinct points of E,, but there is no restriction on the crossing of edges.