Vol. 107, No. 2, 1983

Recent Issues
Vol. 329: 1
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Online Archive
The Journal
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author index
To appear
Other MSP journals
Regular embeddings of a graph

Hiroshi Maehara

Vol. 107 (1983), No. 2, 393–402

In this paper we study embeddings of a graph G in Euclidean space Rn that are ‘regular’ in the following sense: given any two distinct vertices u and v of G, the distance between the corresponding points in Rn equals α if u and v are adjacent, and equals β otherwise. It is shown that for any given value of s = (β2 α2)∕β2, the minimum dimension of a Euclidean space in which G is regularly embeddable is determined by the characteristic polynomials of G and .

Mathematical Subject Classification 2000
Primary: 05C10
Secondary: 05C50
Received: 10 September 1981
Published: 1 August 1983
Hiroshi Maehara