Regular embeddings of a graph

Hiroshi Maehara

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

DOI: 10.2140/pjm.1983.107.393

Abstract

In this paper we study embeddings of a graph G in Euclidean space Rⁿ that are ‘regular’ in the following sense: given any two distinct vertices u and v of G, the distance between the corresponding points in Rⁿ equals α if u and v are adjacent, and equals β otherwise. It is shown that for any given value of s = (β² −α²)∕β², 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

Milestones

Received: 10 September 1981

Published: 1 August 1983