Research Article

On the dimension of a graph

Paul Erdösa1, Frank Hararya2 and William T. Tuttea3

a1 Mathematical Institute, Budapest, Hungary.

a2 University of Michigan, Ann Arbor, U.S.A..

a3 University of Waterloo, Waterloo, Canada.

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 §2 that several results in the literature are unified by the concept of the dimension of a graph, and state some related unsolved problems.

(Received January 07 1965)