On Isometric Embeddings of Graphs

If $G$ is a finite connected graph with vertex set $V$ and edge set $E$, a standard way of defining a distance ${d_G}$ on $G$ is to define ${d_G}(x,y)$ to be the number of edges in a shortest path joining $x$ and $y$ in $V$. If $(M,{d_M})$ is an arbitrary metric space, then an embedding $\lambda :V \to M$ is said to be isometric if ${d_G}(x,y) = {d_M}(\lambda (x),\lambda (y))$ for all $x,y \in V$. In this paper we will lay the foundation for a theory of isometric embeddings of graphs into cartesian products of metric spaces.