This paper presents certain definitions, results and problems concerning the problem of representing a finite metric space with integer distances within a graph. Results are derived for the special cases of "regular" metric spaces, very small metric spaces, and for those metric spaces contained by cycles and trees. It is shown that a tree is the smallest container of the metric space defined on its leaves.
This presentation seeks a generalized approach to a "scaling" problem. Within the social sciences, problems of finding parsimonious spatial representations of a given set of "proximity data" representing distances between pairs of objects have given rise to a variety of scaling techniques (see , for a discussion of some of these). Usually, it is assumed that the model derived from the statistical approach will be a space defined by a multidimensional coordinate system. Though work with "non-dimensional" scaling (e.g. [l, 21) has not required that the data be represented within a coordinate system, this investigation will be concerned with a further generalization through addressing two issues: (1) finding the smallest graph in which the distances of a given metric space can be modelled, and (2) given a graph, finding those metric spaces for which the graph is the smallest container of the metric space. 1. Definition 1.1. A metric space M = (U, d) consists of a set U and a function d: U x U + R' v (0) such that Vu, v, WE U (1) d(n,u)=O, (2) d(u, v) = d(v, u) and (3) d (u, v) + d(v, w) 2 d (u, w). ) is called the distance between points u and v of U. When we wish to clarify that this distance is relative to the space A4 then we shall use dM(u, v) to refer to d(u, v).