  Let G be a simple, connected graph on n vertices. Let d_G(u,v) denote the
distance between vertices u and v in G. A subgraph H of G is isometric if
d_H(u,v)=d_G(u,v) for every u,v in V(H). We say that G is a distance-preserving
graph if G contains at least one isometric subgraph of order k for every k,
1\le k\le n. In this paper we construct regular distance-preserving graphs of
all possible orders and degrees of regularity. By modifying the Havel-Hakimi
algorithm, we are able to construct distance preserving graphs for certain
other degree sequences as well. We include a discussion of some related
conjectures which we have computationally verified for small values of n.
