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 da on G is to define dG (x, y) to be the number of edges in a shortest path joining x and y in V. If (M, dM) is an arbitrary metric space, then an embedding X: V-> M is said to be isometric if dG (x, y) = dM (\ (x), X (y) ) for all x, y e V. In this paper we will lay the foundation for a theory of isometric embeddings of graphs into cartesian products of metric spaces. Introduction. With a finite connected undirected graph1 G = (V, E) one can associate a metric dG: V X V - N (the set of nonnegative integers) by defining dG (x, y) to be the number of edges in a shortest path between x and y for all x, y g V, the vertex set of G. If (M, dM) is an arbitrary metric space we say that an embedding A: V -* M is isometric1 if, for all x, j e I7, (i) (MxUi^'rfʲ). We denote this by writing X: V - A/. A number of papers have appeared in the past few years which deal with various properties of graphs that have isometric embeddings in certain metric and semimet-ric3 spaces (e. g. , see Asl, As2, As3, ADel, ADe2, ADzl, ADz2, Avl, Av2, BGK, Dew, Dezl, Dez2, Dj, F, GP1, GP2, Kl, K2, K3, Y). In this paper we will lay the foundation for a theory of isometric embedding of graphs into cartesian products of metric spaces. Although our primary focus will be on embeddings into products of graphs we should remark that many of the results actually extend to products of more general metric and semimetric spaces. Embedding into cartesian products. For a connected graph G = (V, E) define a relation4 0 on E as follows: Ife= x, y) e and e' = {x', y' e E, then e 0 e' if dc (x, x') + dc{y, /) * dG{x, y') + dc (x', y). The relation 0 is easily seen to be well defined, reflexive and symmetric; let 6 be its transitive closure, and let E, 1 < i < r, be the equivalence classes of 6. Thus, E = UUE, For each /', 1 < i < r, let G denote the graph (V, E \ E) and let C, (l), C, (2),. . . , C, (w, ) denote the connected components of Gt. Finally, form the