Hostname: page-component-7c8c6479df-ph5wq Total loading time: 0 Render date: 2024-03-28T20:11:13.196Z Has data issue: false hasContentIssue false

On the dimension of a graph

Published online by Cambridge University Press:  26 February 2010

Paul Erdös
Affiliation:
Mathematical Institute, Budapest, Hungary.
Frank Harary
Affiliation:
University of Michigan, Ann Arbor, U.S.A..
William T. Tutte
Affiliation:
University of Waterloo, Waterloo, Canada.
Get access

Extract

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.

Type
Research Article
Copyright
Copyright © University College London 1965

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Erdös, P., “Graph theory and probability”, Canad. J. Math., 11 (1959), 3438.CrossRefGoogle Scholar
2.Erdös, P., “On sets of distances of n points in Euclidean space”, Publ. Math. Inst. Hung. Acad. Sci., 5 (1960), 165169.Google Scholar
3.Erdös, P., “Some unsolved problems”, Publ. Math. Inst. Hung. Acad. Sci., 6 (1961), 221254, esp. p. 244.Google Scholar
4.Erdös, P.,.“On circuits and subgraphs of chromatic graphs”, Mathematika, 9 (1962), 170175.CrossRefGoogle Scholar
5.Hadwiger, H., “Ungelöste Probleme No. 40”, Elemente der Math., 16 (1961), 103104.Google Scholar
6.Moser, L. and Moser, W., “Solution to Problem 10”, Canad. Math. Bull., 4 (1961), 187189.Google Scholar