## S369550579.online.de

A simple

*O*(

*mn*) algorithm for recognizing
Institut f¨ur Mathematik und Angewandte Geometrie
We show that any isometric irredundant embedding of a graph into
a product of complete graphs is the canonical isometric embedding.

This result is used to design a simple

*O*(

*mn*) algorithm for recognizingHamming graphs.

All graphs considered in this paper are finite undirected graphs without
loops and multiple edges. Throughout the paper, for a given graph

*G*, let

*n*
and

*m *stand for the number of its vertices and edges, respectively.

Graphs that can be embedded isometrically in a Cartesian product of
complete graphs are called Hamming graphs. Interest in Hamming graphs
has been decisively stimulated by the work of Graham and Pollak [10, 11]

*∗*This work was supported in part by the Ministry of Science and Technology of Slovenia
in communication theory and Firsov [8] in linguistics. In biology, Hamming
graphs appear as “quasi-species” [6].

Several algorithms for recognizing Hamming graphs have been proposed.

The first algorithm is due to Winkler [16]. Its running time is bounded by

*O*(

*n*5). Aurenhammer, Formann, Idury, Sch¨affer and Wagner [2] improved
Winkler’s algorithm to run in

*O*(

*D*(

*m, n*) +

*n*2) time, where

*D*(

*m, n*) is the
time needed to compute the distance matrix of the graph. Wilkeit [14]
presented another algorithm running in

*O*(

*n*3) time.

In 1985 Graham and Winkler [12] published a fundamental paper on
isometric embeddings into Cartesian product graphs. Using their results to-
gether with a result of Aurenhammer and Hagauer [4] one can give an

*O*(

*mn*)
algorithm to recognize Hamming graphs. Aurenhammer and Hagauer [3]
also proposed another algorithm of the same complexity to recognize binary
In this paper we present an

*O*(

*mn*) algorithm to recognize Hamming
graphs. Our algorithm is also based on the theory of isometric embeddings
into Cartesian product graphs. However, our approach needs a minimum
of theory and the algorithm itself is simple and straightforward. We have
taken care that everything up to and including Section 4 is self-contained.

In particular, this includes all results about binary Hamming graphs.

In the next section we state the necessary definitions and recall a connec-
tion between Hamming graphs and the Cartesian product of graphs. In Sec-
tion 3 we introduce the relation Θ and reprove a characterization of binary
Hamming graphs. Section 4 follows with an algorithm for the recognition
of binary Hamming graphs. In the last section we prove that any isometric
irredundant embedding of a graph into a product of complete graphs is the
canonical isometric embedding. With the aid of this result we extend the
algorithm for binary Hamming graphs to all Hamming graphs.

Let Σ be a finite alphabet and let

*w*1 and

*w*2 be words of equal lengthover Σ. Then the

*Hamming distance *between

*w*1 and

*w*2,

*H*(

*w*1

*, w*2), is thenumber of positions

*k *in

*w*1 and

*w*2 such that the

*k*-th symbol in

*w*1 differsfrom the

*k*-th symbol in

*w*2. A graph

*G *is called a

*Hamming graph*, if eachvertex

*v ∈ V *(

*G*) can be labelled by a word of fixed length,

*a*(

*v*), such that

*H*(

*a*(

*u*)

*, a*(

*v*)) =

*dG*(

*u, v*) for all

*u, v ∈ V *(

*G*). Here

*dG*(

*u, v*) denotes the usualshortest path distance in

*G *between

*u *and

*v*. In particular, if Σ =

*{*0

*, *1

*}*,
we call

*G *a

*binary Hamming graph*.

The

*Cartesian product G ✷ H *of graphs

*G *and

*H *is the graph with
vertex set

*V *(

*G*)

*× V *(

*H*) and (

*a, x*)(

*b, y*)

*∈ E*(

*G ✷ H*) whenever

*ab ∈ E*(

*G*)
and

*x *=

*y*, or

*a *=

*b *and

*xy ∈ E*(

*H*). The Cartesian product is commutative,
associative and

*K*1 is a unit. Also,

*G✷H *is connected if and only if both

*G*and

*H *are connected. For

*G*1

*✷G*2

*✷ · · · ✷Gk *we shall also write

*i*=1

*Gi *let

*pi *:

*V *(

*G*)

*→ V *(

*Gi*),

*i ∈ {*1

*, *2

*, . . . , k}*, be the
natural projection of

*G *onto the

*i*-th factor

*Gi*, i.e. for

*v *= (

*v*1

*, v*2

*, . . . , vk*)

*∈V *(

*G*) we set

*pi*(

*v*) =

*vi ∈ V *(

*Gi*). For

*X ⊆ V *(

*G*) let

*pi*(

*X*) =

*{pi*(

*x*)

*| x ∈ X}*.

In particular, for

*e *=

*uv ∈ E*(

*G*) let

*pi*(

*e*) =

*{pi*(

*u*)

*, pi*(

*v*)

*}*. We also introducea

*product coloring c *:

*E*(

*G*)

*→ {*1

*, *2

*, . . . , k} (with respect to the product*
*representation) *as follows. For

*uv ∈ E*(

*G*) we set

*c*(

*uv*) =

*i *if and only
if

*u *and

*v *differ in coordinate

*i*. Clearly

*c *is a mapping from

*E*(

*G*) into

*{*1

*, *2

*, . . . , k}*. It is not an edge coloring in the usual sense, because incident
A subgraph

*H *of a graph

*G *is an

*isometric *subgraph, if

*dH*(

*u, v*) =

*dG*(

*u, v*) for all

*u, v ∈ V *(

*H*). In addition, if

*α *:

*V *(

*H*)

*→ V *(

*G*) maps edgesinto edges and

*α*(

*H*) is an isometric subgraph of

*G*, we call

*α *an

*isometric*
*embedding *of

*H *into

*G*.

The following observation is a starting point in studying isometric sub-
graphs of Cartesian products of graphs.

*i*=1

*Gi, k ≥ *1

*, let u *= (

*u*1

*, u*2

*, . . . , uk*)

*and v *=
(

*v*1

*, v*2

*, . . . , vk*)

*be arbitrary vertices of G. Then dG*(

*u, v*) =
With Lemma 2.1 it is an easy exercise to characterize Hamming graphs:
Theorem 2.2

*A graph G is a Hamming graph if and only if G is an iso-*
*metric subgraph of a Cartesian product of complete graphs.*
Theorem 2.2 in particular implies that binary Hamming graphs are iso-
metric subgraphs of hypercubes (the

*k*-dimensional hypercube

*Qk*,

*k ≥ *1, isthe Cartesian product of

*k *copies of

*K*2).

In this section we present a characterization of binary Hamming graphs
which is essential for a fast recognition algorithm.

Let

*G *be a connected graph. Define a relation Θ on

*E*(

*G*) as follows. If

*e *=

*uu ∈ E*(

*G*) and

*e *=

*vv ∈ E*(

*G*), then

*e*Θ

*e *if and only if

*d*(

*u, v*) +

*d*(

*u , v *) =

*d*(

*u, v *) +

*d*(

*u , v*)

*.*
This relation, which was first introduced in an alternative form in [5], plays a
central role in our investigation. The relation Θ is well-defined, reflexive and
symmetric, yet it need not be transitive. We denote its transitive closure by
Lemma 3.1

*Let P be a shortest path in a graph G. Then no two different*
*edges of P are in relation *Θ

*.*
Proof. Let

*u*0

*u*1

*· · · um *be a shortest path, and let

*e *=

*uiui*+1,

*e *=

*ujuj*+1,

*i < j*. Then

*d*(

*ui, uj*) +

*d*(

*ui*+1

*, uj*+1) = (

*d*(

*ui*+1

*, uj*) + 1) + (

*d*(

*ui, vj*+1

*− *1)

*,*
hence

*e *is not in the relation Θ with

*e *.

It follows from Lemma 3.1 that for a tree on

*n *vertices Θ

*∗ *consists of

*n − *1 equivalence classes, each containing a single edge. Lemma 3.1 also
implies that two adjacent edges are in relation Θ if and only if they lie in a
Lemma 3.2

*Suppose P is a path connecting the endpoints of an edge e.*
*Then P contains an edge f with e*Θ

*f .*
Proof. Let

*u*0

*u*1

*· · · umu*0 be a closed path with

*e *=

*umu*0 and

*ei *=

*ui−*1

*ui*for

*i *= 1

*, *2

*, . . . , m*. Set

*µ*(

*e, ei*) =

*d*(

*um, ui−*1) +

*d*(

*u*0

*, ui*)

*− d*(

*um, ui*)

*− d*(

*u*0

*, ui−*1)
Clearly

*s *= 2, which means that at least one of the summands

*µ*(

*e, ei*) = 0,i.e.

*e*Θ

*ei*.

For an edge

*uv *of a graph

*G *let

*Vuv *=

*{ w | w ∈ V *(

*G*)

*, dG*(

*w, u*)

*< dG*(

*w, v*)

*}.*
Lemma 3.3

*Let e *=

*uv be an edge of a connected bipartite graph G and let*
*Ee *=

*{ f | f ∈ E*(

*G*)

*, e*Θ

*f }.*
*Then G\Ee has exactly two components. Furthermore, they are induced bythe vertex sets Vuv and Vvu.*
Proof.

*G\Ee *is disconnected by Lemma 3.2.

Let

*w ∈ Vuv *and let

*P *be a shortest

*u − w *path. Then

*vP *is a shortest

*v − w *path. Hence, using Lemma 3.2 again, no edge of

*P *is in relation Θ
with

*e*. It follows that

*P *connects

*u *and

*w *in

*G\Ee*.

Since

*G *is bipartite,

*d*(

*w, u*) =

*d*(

*w, v*). Therefore

*Vuv *and

*Vvu *form a
partition of

*V *(

*G*). In addition, no edge

*ww ∈ E*(

*G*), where

*w, w ∈ Vuv*, isin relation Θ with

*e*, and the proof is complete.

For Cartesian product graphs Lemma 2.1 immediately implies:

*i*=1

*Gi and let e, e ∈ E*(

*G*)

*.*
*(i) If c*(

*e*) =

*c*(

*e *) =

*i and pi*(

*e*) =

*pi*(

*e *)

*then e*Θ

*e .*

(ii) If c(

*e*) =

*c*(

*e *)

*then e*Θ

*e does not hold.*
Consider the product

*G ✷ H *of two graphs. Then Lemma 3.4 (i) claims
that if

*ab ∈ E*(

*G*), then (

*a, x*)(

*b, x*) is in relation Θ with (

*a, y*)(

*b, y*), for any

*x, y ∈ V *(

*H*). Lemma 3.4 (ii) on the other hand says that if

*ab ∈ E*(

*G*)
and

*xy ∈ E*(

*H*), then (

*a, z*)(

*b, z*) is not in relation Θ with (

*c, x*)(

*c, y*), for
any

*c ∈ V *(

*G*) and

*z ∈ V *(

*H*), i.e. edges with different colors with respect
to the product coloring are not in relation Θ. In other words, every color
class (with respect to the product coloring) is the union of one or more
equivalence classes with respect to Θ

*∗*.

Theorem 3.5 [16, Winkler]

*A graph G is a binary Hamming graph if and*
*only if G is bipartite and *Θ

*∗ *= Θ

*.*
Proof. Assume

*G *is an isometric subgraph of a hypercube. Then

*G *is
Define a relation

*R *on

*E*(

*G*) as follows. For

*e, e ∈ E*(

*G*) let

*eRe *if and
only if

*c*(

*e*) =

*c*(

*e *). Let

*c*(

*e*) =

*c*(

*e *) =

*i*. Then

*pi*(

*e*) =

*pi*(

*e *) =

*{*0

*, *1

*} *andhence, by Lemma 3.4 (i),

*e*Θ

*e *. Furthermore, by Lemma 3.4,

*e *and

*e *are
not related by Θ if

*c*(

*e*) =

*c*(

*e *). It follows

*R *= Θ. As

*R *is transitive, we
Conversely, let

*G *be bipartite and let Θ

*∗ *= Θ. Let

*e*1 =

*x*1

*y*1,

*e*2 =

*x*2

*y*2,

*. . .*,

*ek *=

*xkyk*,

*k ≥ *1 be representatives of each equivalence class of Θ

*∗*.

Define an embedding

*α *:

*V *(

*G*)

*→ Qk *=

*{*0

*, *1

*}k *in the following way. Let

*v ∈ V *(

*G*). For

*i *= 1

*, *2

*, . . . , k *let the

*i*-th coordinate of

*α*(

*v*) be 0 if

*v ∈ Vxiyi*and 1 if

*v ∈ Vy *. We claim that

*α *is an isometric embedding.

Let

*uv ∈ E*(

*G*) and assume

*uv *belongs to the equivalence class of

*ei*.

By Lemma 3.3,

*α*(

*u*) and

*α*(

*v*) differ in the

*i*-th coordinate. Furthermore, if

*j *=

*i *then

*d*(

*u, xj*) +

*d*(

*v, yj*) =

*d*(

*u, yj*) +

*d*(

*v, xj*). Thus

*α*(

*u*) and

*α*(

*v*) havesame

*j*-th coordinate. It follows that

*α *maps edges to edges.

As

*G *is bipartite and Θ = Θ

*∗*, no two adjacent edges are in the same
equivalence class. Furthermore, if

*P *is a shortest path between

*u *and

*v*
then, by Lemma 3.1,

*α*(

*u*) and

*α*(

*v*) differ in just as many coordinates as the
number of edges of

*P *, i.e., the distance

*dG*(

*u, v*).

In a direct implementation of Theorem 3.5 we must check for all pairs of
edges whether they are in relation Θ. For a given graph

*G *this leads to an
algorithm with time complexity

*O*(

*m*2). In order to improve this complexity,
we introduce relation Θ1, which is due to Feder [7].

Let

*T *be a spanning tree of a graph

*G*. Then edges

*e, e ∈ E*(

*G*)
are in the relation Θ1 if and only if they are in the relation Θ and if atleast one of the edges

*e *and

*e *belongs to

*T *. Let

*E*1

*, E*2

*, . . . , Ek *be theequivalence classes of the relation Θ

*∗*1. For

*i *= 1

*, *2

*, . . . , k *let

*Gi *denotethe graph (

*V *(

*G*)

*, E*(

*G*)

*\Ei*) and let

*Ci,*1

*, Ci,*2

*, . . . , Ci,m *denote the con-
nected components of

*Gi*. Form the graphs

*G∗i*,

*i *= 1

*, *2

*, . . . , k*, by letting

*V *(

*G∗i*) =

*{Ci,*1

*, Ci,*2

*, . . . , Ci,m } *and taking

*C*
*i,j Ci,j *to be an edge of

*G∗i *if
some edge in

*Ei *joins a vertex in

*Ci,j *to a vertex in

*Ci,j *.

We now define the natural contraction

*αi *:

*V *(

*G*)

*→ V *(

*G∗i*) by setting

*αi*(

*v*) =

*Ci,j *if

*v ∈ Ci,j*. Finally, we obtain a mapping

*α *:

*V *(

*G*)

*→*
*α*(

*v*) = (

*α*1(

*v*)

*, α*2(

*v*)

*, . . . , αk*(

*v*))

*.*
It is important for our algorithm that

*k ≤ n−*1. Indeed, let

*e *=

*uv ∈ Ei*.

By Lemma 3.2 any path in

*G *from

*u *to

*v *must traverse at least one edge
from

*Ei*. This is in particular true for the path between

*u *and

*v *in

*T *, hencethere is at least one edge of

*T *belonging to

*Ei*.

This also means that Θ = Θ

*∗*1 in a binary Hamming graph. For, suppose

*e*Θ

*f *. Then there is an

*e ∈ T *with

*e *Θ

*e*. Since Θ = Θ

*∗ *we also have

*e *Θ

*f*
and

*e*Θ

*∗*1

*f*. Hence Θ

*⊆ *Θ

*∗*1. Since Θ1

*⊆ *Θ we also have Θ

*∗*1

*⊆ *Θ

*∗ *= Θ, whichproves the assertion.

*Input*: a connected graph

*G*.

*Output*: TRUE, and a labeling, if

*G *is a binary Hamming graph. FALSE,
1. If

*G *is not bipartite then return FALSE and stop.

2. Compute Θ

*∗*1.

3. Compute

*Gi*,

*i *= 1

*, *2

*, . . . , k *and

*α*(

*v*),

*v ∈ V *(

*G*).

4. For

*i *= 1

*, *2

*, . . . , k*, compute

*mi*, i.e., the number of components in

*Gi*. If for some

*i*,

*mi > *2, then return FALSE and stop.

5. Return TRUE and the labeling of

*G *obtained in step 3.

Theorem 4.1

*Algorithm BHG correctly recognizes binary Hamming graphs*
*and can be implemented to run in O*(

*mn*)

*time using O*(

*m*)

*space.*
Proof. Suppose that

*G *is a binary Hamming graph. Then Θ = Θ

*∗*1 andevery

*Gi *has exactly two components by Lemma 3.3. It thus remains toshow that

*α *is an isomorphism, if every

*Gi *has exactly two components.

Let

*P *be a shortest path between

*u *and

*v *in

*G*. By Lemma 3.1 no two
edges of

*P *are in the relation Θ and thus all edges of

*P *belong to different
Θ

*∗*1 classes. This means that the labels of

*u *and

*v *differ in just as manycoordinates as the number of edges of

*P *, i.e. the distance

*dG*(

*u, v*). Thisproves the correctness of the algorithm.

Concerning the running time we first note that it is trivial to check
bipartiteness in

*O*(

*m*) time and space.

Let

*T *be a spanning tree of

*G *and let

*uv *be an edge of

*T *. Then we
can calculate the distances from

*u *and

*v *to all other vertices in

*O*(

*m*) time
and

*O*(

*m*) space. Hence we get all the edges in

*G *related to

*e *under Θ1in the same time, and in time

*O*(

*mn*) over all edges in

*T *. To get the
equivalence classes of Θ

*∗*1 we merge equivalence classes of two edges wheneverwe determine that they are in the relation Θ1. During the execution of theprocedure there will be at most

*m − *1 such union operations and

*m*(

*n − *1)
find operations. It is well-known that these can be done in

*O*(

*nm*) time
using

*O*(

*m*) space (see, for example, [1]).

When

*Ei *is known, it is easy to construct the graph

*Gi *in

*O*(

*m*) time. As

*k ≤ n − *1, all the

*Gi *can be obtained in

*O*(

*mn*) time. Since every edge in

*Gi*corresponds to an edge of

*G*, we get all the

*Gi *using

*O*(

*m*) space. In addition,we don’t need to store the complete information on

*α*(

*v*), it is enough to store
the value

*αi*(

*v*) if it is different from

*αi*(

*u*) for some

*uv ∈ E*(

*G*).

Graham [9] proved that there exists a fixed small

*c *such that

*m ≤*
*c n *log

*n *for any subgraph of a hypercube. Thus:
Corollary 4.2

*Algorithm BHG can be implemented to run in O*(

*n*2 log

*n*)

*time using O*(

*n *log

*n*)

*space.*
We are going to modify Algorithm BHG to recognize general Hamming
Let

*α *be the mapping (

*∗*) defined in Section 4. Call an isometric em-

*i irredundant *if

*|Hi| ≥ *2,

*i *= 1

*, *2

*, . . . , m*, and
for all

*h ∈ V *(

*Hi*),

*h *occurs as a coordinate value of the image of some

*g ∈ V *(

*G*). This is the principal result in the theory of isometric embeddings
Theorem 5.1 [12, Graham and Winkler]

*The mapping α is an isometric*
*i , the so-called *canonical embedding

*. Further-*
*more, the embedding α is irredundant and has the largest possible number of*
*factors among all irredundant isometric embeddings of G.*
Graham and Winkler [12] proved Theorem 5.1 for the relation Θ, while
Feder [7] showed Θ

*∗*1 = Θ

*∗*.

For the isometric embeddings into products of complete graphs we have:
Theorem 5.2 [16, Winkler]

*Any two isometric embeddings of a graph into*
*products of complete graphs are equivalent.*
Equivalence in Theorem 5.2 essentially means that equivalent isometric
embeddings can be obtained from one another by discarding unused factors,
permuting factors, and permuting vertices within a factor.

The following theorem is crucial for our algorithm.

*i*=1

*Hi be an isometric irredundant embedding*
*of a graph G into a product of complete graphs Hi. Then this embedding isthe canonical isometric embedding.*
Proof. By Theorem 5.2 we have to show that any two edges

*e*,

*e *in

*β*(

*G*)
are in the relation Θ

*∗ *if they have the same color with respect to the product
Consider now

*i*-layers

*U *and

*V *with respect to

*Hi*. We claim that

*pi*(

*β*(

*G*)

*∩ U*)

*⊆ pi*(

*β*(

*G*)

*∩ V *) or vice versa. If this is not the case, thereare vertices

*u, u ∈ U *and

*v, v ∈ V *such that

*u ∈ β*(

*G*)

*∩ U, u /*
*v ∈ β*(

*G*)

*∩ V, v /*
where

*pi*(

*u*) =

*pi*(

*v *),

*pi*(

*u *) =

*pi*(

*v*) (see Fig. 1).

Suppose the distance between

*U *and

*V *in

*i*=1

*Hi *is

*k*. Then

*k *+ 1 =

*dH*(

*u, v*) =

*dβ*(

*G*)(

*u, v*)

*, *which is only possible if

*u ∈ β*(

*G*) or

*v ∈ β*(

*G*).

This proves the claim.

Thus, let the

*i*-colored edges

*e, e *in

*β*(

*G*) be in the

*i*-layers

*U *and

*V *,
respectively. If

*pi*(

*β*(

*G*)

*∩ U*)

*⊆ pi*(

*β*(

*G*)

*∩ V *), then by Lemma 3.4 (i) thereis an edge

*e *in

*β*(

*G*)

*∩ V *with

*e*Θ

*e *. Since

*β*(

*G*)

*∩ V *is complete we have

*e *Θ

*e *, and hence

*e*Θ

*∗e *.

*Input*: a connected graph

*G*.

*Output*: TRUE, and a labeling, if

*G *is a Hamming graph. FALSE, otherwise.

1. Compute Θ

*∗*1.

2. Compute

*Gi*,

*i *= 1

*, *2

*, . . . , k *and

*α*(

*v*),

*v ∈ V *(

*G*).

3. If for some

*i *= 1

*, *2

*, . . . , k*,

*G∗i *is not a complete graph, then return
4. Return TRUE and the labeling of

*G *obtained in step 2.

Theorem 5.4

*Algorithm HG correctly recognizes Hamming graphs and can*
*be implemented to run in O*(

*mn*)

*time using O*(

*m*)

*space.*
Proof. Correctness of the algorithm follows from Theorem 5.3.

The complexity can be argued as in the proof of Theorem 4.1 with the
exception of Step 3. Every edge of a factor graph

*G∗i *correspond to anedge of

*G *and furthermore, this correspondence is injective. It follows
Hence to implement Step 3 in the desired time and
space it is sufficient to count the number of edges in the

*G∗i*’s.

[1] A. Aho, J. Hopcroft and J. Ullman, The Design and Analysis of Com-
puter Algorithms (Addison-Wesley, Reading, 1974).

[2] F. Aurenhammer, M. Formann, R. Idury, A. Sch¨affer and F. Wagner,
Faster isometric embeddings in products of complete graphs, DiscreteAppl. Math., to appear.

[3] F. Aurenhammer and J. Hagauer, Recognizing binary Hamming graphs
in

*O*(

*n*2 log

*n*) time, in: Proc. 16th Int. Workshop on Graph TheoreticalConcepts in Computer Science, Lecture Notes in Comput. Sci., Vol. 484(Springer, New York, 1991) 90–98.

[4] F. Aurenhammer and J. Hagauer, Computing equivalence classes
among the edges of a graph with applications, Discrete Math. 109 (1992)3–12.

[5] D. Djokovi´c, Distance preserving subgraphs of hypercubes, J. Combin.

[6] M. Eigen and R. Winkler-Oswattisch, Transfer-DNA: the early adaptor,
Naturwissenschaften 68 (1981) 217–228.

[7] T. Feder, Product graph representations, J. Graph Theory 16 (1992)
[8] V. Firsov, Isometric embedding of a graph in a Boolean cube (Russian),
[9] R. Graham, On primitive graphs and optimal vertex assignments, Ann.

New York Acad. Sci. 175 (1970) 170–186.

[10] R. Graham and H. Pollak, On the addressing problem for loop switch-
ing, Bell System Tech. J. 50 (1971) 2495–2519.

[11] R. Graham and H. Pollak, On embedding graphs in squashed cubes,
in: Graph Theory and Applications, Lecture Notes in Math., Vol. 303(Springer, New York, 1972) 99–110.

[12] R. Graham and P. Winkler, On isometric embeddings of graphs, Trans.

Amer. Math. Soc. 288 (1985) 527–536.

[13] W. Imrich, Embedding graphs into Cartesian products, Ann. New York
[14] E. Wilkeit, Isometric embeddings in Hamming graphs, J. Combin. The-
[15] P. Winkler, Proof of the squashed cube conjecture, Combinatorica 3
[16] P. Winkler, Isometric embeddings in products of complete graphs, Dis-
crete Appl. Math. 7 (1984) 221–225.

[17] P. Winkler, The metric structure of a graph, in: C. Whitehead, ed.,
Theory and Applications, London Math. Soc. Lecture Note Ser., Vol.

123 (Cambridge University Press, Cambridge, 1987) 197–221.

Source: http://s369550579.online.de/at/uploads/tx_pdforder/P67.pdf

LEVINE EMB Agar (Eosin Methylene-blue Lactose Agar acc. to LEVINE) For the isolation and differentiation of Escherichia coli and Enterobacter and for the rapid identification of Candida albicans according to LEVINE (1918, 1921). in vitro diagnosticum – See also General Instruction of Use For professional use only Warnings and precautions see ChemDAT® (www.chemdat.info)

P r o s t a t e C a n c e r D N A P l o i d y a n d R e s p o n s e t o S a l v a g e H o r m o n e T h e r a p y A f t e r R a d i o t h e r a p y W i t h o r W i t h o u t S h o r t - T e r m T o t a l A n d r o g e n B l o c k a d e : A n A n a l y s i s o f R T O G 8 6 1 0 By A. Pollack, D.J. Grignon, K.H. Heydon, E.H. Hammond, C.A. Lawton, J.B. Mesic, K.K. Fu, A.T. Porter, Purpose: