Deza M.M., Laurent M. Geometry of Cuts and Metrics
Подождите немного. Документ загружается.
19.2
Further
Characterizations
291
For Y E ]Rn, define x E
]Rn+1
by
setting
xr
= L
Yi
- L
Yi
iEA(v
r
)
iEB(v
r
)
for r =
0,1,
...
,no
One
can
check
that
L
Xr
=
0,
i.e., x E U,
and
x =
O<r<n
(0,
...
,0)
implies
that
Y = (0,
...
,0).
Hence,
-we
have found a
1-1
linear corre-
spondence between
the
spaces ]Rn
and
U.
We
check
that,
under
this
correspon-
dence,
Indeed,
do(a
n
as)
appears
in
L (ei'
ej)YiYj
with
the
coefficient
l";i,j";n
L YiYj + L YiYj
(i,j)EA(v
r
)xB(v,)
(i,j)EB(v
r
)xA(v,)
L YiYj - L YiYj,
(i,j)EA(vr)xA(v,)
(i,j)EB(vr)xB(v,)
which is equal
to
-XrXs.
This
shows
the
equivalence
of
(i)
and
(ii).
I
Example
19.2.11.
Consider
the
graph
G
n
:=
K
n
+
1
\K
n
-
1
with
node set
{ao,
...
,an}
and
with
edges
the
pairs (ao,
al),
(ao,
ai)
and
(aI,
ai)
for i =
2,3,
...
,n.
Then,
the
path
metric
of
G
n
is of negative
type
if
and
only
if
n
::;
5.
(To see it, consider
the
oriented spanning tree T with arcs
el
= (ao,
ad,
...
,en
=
(ao, an).
The
matrix
((ei'
ej)
)i,j=l,
...
,n
has all its entries equal
to
° except
the
diag-
onal entries equal
to
1
and
the
(1, i)-
and
(i, I)-entries equal
to
! for i = 2,
...
,n.
Its
determinant
is equal
to
5-:t.)
Note
that,
for n
2:
6, G
n
provides a counterex-
ample
to
the
converse of
the
last implication from Figure 19.2.6, since
the
dis-
tance
matrix
of G
n
has exactly one positive eigenvalue,
but
G
n
is
not
of
negative
type. (Indeed,
the
eigenvalues
of
the
distance
matrix
of
G
n
are
2n
- 1,
-1,-2
with
respective multiplicities 1,1, n - 1.) I
Finally, let us
mention
another
formulation for
the
isometric dimension
of
a
hypercube
embeddable
graph
in
terms
of
the
number
of negative eigenvalues of
its
distance
matrix,
due
to
Graham
and
Winkler [1985].
Proposition
19.2.12.
Let
G
be
a graph
with
distance
matrix
Do
and
let
n+(Do),
n_(Do)
denote
the
number
of
positive
and
negative eigenvalues
of
Do.
If
G is hypercube embeddable,
then
dimJ(G) =
n_(Do)
and
n+(Do)
= 1 hold.
Proof. Suppose
that
dimJ(G) = k. Let
a-
be
an
isometric embedding
of
G into
the
k-hypercube H(k,2); denote by a-(a) = (aI,
...
,ak)
E
{O,I}k
the
image of
each node
a E V
under
this
embedding. For h = 1,
...
,k,
set
Xh
:=
{a
E V I ah =
OJ,
Y
h
:=
{a
E V I ah = I} = V \
Xh.
292
Chapter
19. Isometric
Embeddings
of
Graphs
into
Hypercubes
Then,
L
dc(a,
b)XaXb = L ( L lah - bhl)xaXb = L
(L
xa)(
L
xa)
a,bEV a,bEV
l:<=;h:<=;k l:<=;h:<=;k
aEX
h
bEY
h
=
~(L
Xa)2
-
~
L
(L
Xa
- L
Xb)2
aEV
l:<=;h:<=;k
aEX
h
bEY
h
(where
the
last
equality
is
obtained
using
the
identity
xy
=
i((x+y)2
_(x-y)2))).
Hence,
the
quadratic
form
L
dc(a,
b)XaXb
a,bEV
can
be
written
as
the
sum
of one "positive"
square
and
k "negative" squares. By
Sylvester's law of
inertia,
this
implies
that
n+(Dc)
:S
1
and
n_(Dc)
:S
k.
On
the
other
hand,
n+(Dc)
::::
1 since
Dc
has
trace
zero. Hence,
n+(Dc)
= 1
and
the
rank
of
Dc
satisfies
rank(Dc)
=
n+(Dc)
+
n-(Dc)
:S
k + 1.
We
show
that
rank(Dc)
= k + 1.
This
will
imply
that
n_(Dc)
=
k,
thus
stating
the
result.
We
can
suppose
without
loss of generality
that
a given
node
a(O)
of G receives
the
label
O"(a(O))
:=
(0,
...
,0)
in
the
hypercube
embedding.
We
claim
that
there
exist k nodes
a(l),
...
,a(k)
of G whose labels O"(a(l)),
...
,O"(a(k)) are linearly in-
dependent.
For this,
it
suffices
to
check
that
the
system
{O"(
a)
I a E
V}
<;;:
{O,
I}k
has
full
dimension
k.
Suppose for
contradiction
that,
say,
the
k-th
coordinate
can
be
expressed
in
terms
of
the
others, i.e.,
there
exist scalars
AI,
.
..
,Ak-I
such
that
ak =
l:1:<=;j:<=;k-1
Ajaj
for all a E
V.
Then,
ak = b
k
holds for any two adja-
cent
nodes a, b
in
G.
This
implies
that
ak = ° holds for each
node
a E
V,
by
considering a
shortest
path
from
a(O)
to
a. So, one could have
embedded
G
into
the
(k -
I)-hypercube,
contradicting
the
fact
that
dimJ(G)
=
k.
We now claim
that
the
submatrix
M:=
(dc(a(i)
a(j)))·
'-0
k
,
7.,)-
,
...
,
is nonsingular.
This
will
imply
that
rank(Dc)
::::
k+
1 and, therefore,
rank(Dc)
=
k + 1. For i =
0,1,
...
,
k,
set
where e =
(1,
...
, 1)T. As
the
vectors
u(i)
are
±I-valued,
we have
dc(a(i),a(j))
= L
la~i)_a~)I=~
L
IU~i)_U~)1
I <h<k 2 I <h<k
=
!-
t
(1
-
u~)u~))
= !
-=-
~(u(i)f
u(j).
I:<=;h:<=;k
2 2
Therefore,
k 1
M =
-J
-
-Gram(u(O),u(I),
...
,u(k)),
2 2
where J denotes
the
all-ones
matrix
and
Gram(u(O),u(1),
...
,u(k))
denotes
the
Gram
matrix
of
the
vectors
u(O),
u(1),
..
.
,u(k).
One
can
easily check
that
det(M)
=
(_2)-(k+l)
(det(Gram(u(O),
u(I),
...
,
u(k)))
-k
det(
Gram(
u(1) -
u(O),
u(2) -
u(O),
...
,u(k)
- u(O)))) .
19.3
Additional
Notes
293
But,
det(Gram(uCO),uCl),
...
,uCk))) = ° since
the
vectors
uCO),uCl),
...
,uCk)
are
linearly
dependent,
and
det(Gram(u(1) - u
CO
), u
(2
) -
u
CO
),
...
, u
Ck
) -
uCO)))
=I=-
°
since
the
vectors
uCl)
- u
CO
), u
(2
) - u
CO
),
...
, u
Ck
) -
uCO)
are linearly
independent.
Therefore,
det(M)
=I=-
0. I
19.3
Additional
Notes
We
mention
here
some
remarks
on
possible
relaxations
of
the
notion
of
isometric
embeddability
into
the
hypercube.
First,
one
may
consider
isometric
embed-
dings
into
the
squashed
hypercube;
second, one
may
consider
embeddings
as a
subgraph
(not
necessarily isometric)
into
the
hypercube;
finally,
the
notion
may
be
extended
to
hypergraphs.
Isometric
Embedding
into
Squashed
Hypercubes.
As
we
just
saw,
not
every
graph
can
be
isometrically
embedded
into
a
hypercube.
For
this
reason,
Graham
and
Pollak
[1971]
considered isometric
embeddings
into
squashed
hy-
percubes.
Let
d.
denote
the
distance
defined
on
the
set
B.
= {a, 1,
*}
by
setting
d.(x
) = { 1
if{x,y!
= {a,
I}
, Y ° otherwIse
for
x,
Y E B •. Hence,
the
symbol
* is
at
distance
° from
the
other
symbols;
it
is
also called
the
"don't
care" symbol.
The
distance
d.
can
be
extended
to
B';'
by
setting
d.((Xl,
...
,Xm),(Yl,···,Ym))=
L d.(Xi,Yi).
lSiSm
The
distance
space (B';',
d.)
is called
the
squashed m-hypercube.
It
contains
the
usual
m-hypercube
as a subspace.
Each
element (Xl,
...
,
Xm)
E B';'
can
be
thought
of
as
representing
a face
of
the
m-dimensional
hypercube,
namely,
the
face
consisting
of
all y E {o,l}m
such
that
Yi
=
Xi
for all i
such
that
Xi
E {a,
I}.
A nice
property
of
squashed
hypercubes
is
that
every
connected
graph
can
be
isometrically
embedded
in
some
squashed
hypercube.
Indeed,
let
G
be
a
connected
graph
with
node
set
{I,
...
, n}. Set
m'-
L
dc(i,j).
lSi<jSn
For
1
::;
i < j
::;
n,
let
Dij
be
pairwise disjoint
subsets
of
{I,
...
,
m}
with
IDijl
=
dc(i,j).
Label
each
node
i
by
the
m-tuple
(il"'"
i
m
) E B';'
by
setting
.
{O
~f
k E
U~~{+l
Dih
~k
= 1 If k E Uh=l
Dih
otherwise.
Then,
d.((il,
...
,i
m
),(jl,
...
,jm))
=
IDijl
=
dc(i,j).
This
shows
that
G
can
be
isometrically
embedded
into
the
squashed
m-hypercube.
Let r(
G)
denote
294
Chapter
19. Isometric
Embeddings
of
Graphs
into
Hypercubes
the
smallest dimension
of
a squashed hypercube in which G
can
be embedded.
Winkler
[1983]
showed
that
r(
G) S n - 1 for each
graph
on
n nodes.
On
the
other
hand,
r(G)?
max(n+(Dc),n_(Dc)),
where
n+(Dc),n_(Dc)
denote
the
number
of
positive
and
negative eigenvalues
of
the
distance
matrix
Dc
of G
(Graham
and
Pollack [1972]). For instance, r(Kn) = n - 1 since
n_(DKn)
=
n -
1.
The
following provides
an
isometric embedding
of
K3
into
the
squashed
2-hypercube:
1
......
(0,0),2
......
(0,1),3
......
(1,*).
Nonisometric
Embedding
of
Graphs
into
Hypercubes.
Another
relax-
ation
of
the
notion
of
hypercube
embeddable
graphs
is
that
of cubical graphs.
A
graph
G is said to be cubical
if
G is a
subgraph
of
some hypercube
H(m,2),
i.e.,
there
exists
an
injective
mapping
from
the
node set
of
G
to
the
node
set
of
H(m,
2)
which
maps
edges
of
G to edges
of
H(m,
2). Clearly, every cubical
graph
is
bipartite
and
every hypercube embeddable
graph
is cubical. We show
below
an
example
of
a
graph
which is cubical
but
not
hypercube
embeddable.
1000
1001
~
OOOO~oool
OOID
0011
The
structure
of
the
minimal
noncubical graphs
has
been
studied
in
Garey
and
Graham
[1975], where some constructions
of
such
graphs
are presented. For
instance,
K
2
,3
and
odd
circuits are
minimal
noncubical graphs. Recall from
Remark
19.1.5
that
one
can
check
in
polynomial
time
whether
a
graph
G is
hypercube
embeddable
and,
moreover,
the
minimum
dimension mh(G)
of
a hy-
percube
containing G as
an
isometric
subgraph
can
be
computed
in
polynomial
time.
On
the
other
hand,
it
has
been
proved
that
deciding
whether
a
graph
G
is cubical is
an
NP-complete problem (Afrati,
Papadimitriou
and
Papageorgiou
[1985, 1989];
Krumme,
Venkataraman
and
Cybenko [1986]). Moreover, for G
cubical,
computing
the
minimum
dimension
of
a hypercube containing G as a
subgraph
is also a difficult problem. For instance, each
tree
is cubical (in fact,
a
tree
on
n nodes
can
be
isometrically embeded into
an
(n -
I)-hypercube).
But,
given a
tree
T
and
an
integer
m,
it is NP-complete
to
decide
whether
T
is a
subgraph
of
the
m-hypercube
(Wagner
and
Corneil [1990]).
The
problem
of
determining
the
minimum
dimension
of
a
hypercube
containing a tree
has
been
long
studied
(see, e.g., Havel
and
Liebl [1972, 1973]). Along
the
same
lines,
given a
graph
G
and
integers
m,
k,
it is NP-complete
to
decide
whether
G is a
subgraph
of
(Km)k (Wagner
and
Corneil [1993]).
Isometric
Embeddings
into
Cube-Hypergraphs.
The
characterization
of
the
graphs
that
can
be
isometrically
embedded
into
the
hypercube
has
been
ex-
tended
in
the
context
of
uniform
hypergraphs
by Burosch
and
Ceccherini [1995].
19.3 Additional Notes
295
At-uniform
hypergraph
H =
(V,
E)
consists
of
a set V
of
vertices
and
a set E
of
(hyper)edges each having
the
same
cardinality t
~
2.
A semimetric dH
can
be
defined on V
in
the
following way:
Construct
the
graph
G H with vertex set V
and
with
two nodes
x,
y E V being adjacent
if
they
are contained
in
a
common
edge
of
H.
Then,
we
take for dH
the
path
metric of
the
graph
GH.
A hyper-
graph
H =
(V,
E)
is
said
to
be
isometrically embeddable into
another
hypergraph
H'
=
(V'
,[')
if
the
graph
G H
can
be
isometrically
embedded
into G
H"
As hy-
pergraph
analogue
ofthe
hypercube, Burosch
and
Ceccherini
[1995]
considers
the
following t-uniform
hypergraph
Q(n,
t):
its vertex set
is
{O,
1,
...
, t
_l}n
and
an
edge consists
of
all
the
vectors x E
{O,
1,
...
, t
_1}n
whose coordinates are fixed
on
n - 1 positions with
the
last coordinate being free
in
{O,
1,
...
, t
-I}.
Hence,
two vectors
x, y belong to a common edge of Q(n, t) if
and
only if
their
Hamming
distance is
1.
In
other
words,
the
graph
structure
GQ(n,t)
underlying
the
hyper-
graph
Q(n, t) is
the
Hamming
graph
H(n,
t). Burosch
and
Ceccherini charac-
terize
the
t-uniform hypergraphs
that
can
be
embeded into
the
cube-hypergraph
Q(n,
t);
their
characterization is a direct extension
of
the
corresponding results
in
the
graph
case, namely,
of
the
results by Djokovic (Theorem 19.1.1)
and
by
Graham
and
Winkler (Corollary 20.1.3 (iv)).
M.M. Deza, M. Laurent, Geometry of Cuts and Metrics, Algorithms and Combinatorics 15,
DOI 10.1007/978-3-642-04295-9_20, © Springer-Verlag Berlin Heidelberg 2010
Chapter
20.
Isometric
Embeddings
of
Graphs
into
Cartesian
Products
We have characterized
in
the
previous
chapter
the
graphs
that
can
be
isometri-
cally
embedded
into a hypercube.
The
hypercube
is
the
simplest example
of
a
Cartesian
product
of
graphs; indeed,
the
m-hypercube
is
nothing
but
(K2)m. We
consider here isometric embeddings
of
graphs
into
arbitrary
Cartesian
products.
It
turns
out
that
every
graph
can
be
isometrically
embedded
in
a canonical way
into a
Cartesian
product
whose factors are "irreducible", i.e.,
cannot
be
further
embedded
into
Cartesian
products.
We present two applications of
this
result,
for finding
the
prime
factorization of a graph,
and
for showing
that
the
path
met-
ric
of
every
bipartite
graph
can
decomposed
in
a unique way as a nonnegative
combination
of
primitive
semimetrics.
20.1
Canonical
Metric
Representation
of
a
Graph
Let
G,
HI"'"
Hk
be
graphs.
An
isometric
embedding
of
G into
the
Cartesian
product
III
<i<k
Hi is said
to
be
irredundant if each factor Hh is a connected
graph
on
at-least
two nodes,
and
if
each vertex
of
every factor Hh
appears
as
a
coordinate
in
the
image
of
at
least one node
of
G. Clearly, any isometric
embedding
into a
Cartesian
product
can
be
made
irredundant
by
discarding
the
factors consisting
of
an
isolated node
and
the
unused nodes
in
each factor.
An
irredundant
isometric
embedding
of
G into a
Cartesian
product
is
also called
a metric representation of G. Two isometric embeddings of G into
Cartesian
products
are said
to
be
equivalent if
there
is
a bijection between
the
factors
of
one
and
the
factors of
the
other,
together
with
isomorphisms between
the
corresponding factors for which
the
obvious
diagram
commutes. A
graph
G
is
said
to
be
irreducible if all its
metric
representations are equivalent
to
the
trivial
embedding
of
G into itself.
Examples
of
irreducible
graphs
include:
the
complete
graph
Kn (n
;:::
2),
odd
circuits C
2n
+
I
(n
;:::
1),
the
half-cube
~H(n,
2)
(n
;:::
2),
the
cocktail-party
graph
Knx2 (n;::: 3),
the
Petersen
graph
PlO,
the
Gosset
graph
G
56
,
the
Schliifli
graph
G
27
,
etc. Actually,
it
is observed
in
Graham
and
Winkler
[1985]
that
the
probability
that
a
random
graph
(with
edge
probability
1/2)
on
n nodes is
irreducible goes
to
1 as n ---->
00.
The
following
theorem
is
the
main
result
of
this
section;
it
is
due
to
Graham
and
Winkler
[1985]; see also
Winkler
[1987b]
and
Graham
[1988].
298
Chapter
20.
Isometric Embeddings of Graphs into Cartesian
Products
Theorem
20.1.1.
Every connected graph G has a unique metric representation
in
which each factor Gh is irreducible;
it
is called the canonical metric represen-
tation
of
G. Moreover, k = dimJ(G) and,
if
is another metric representation
of
G, then there exist a partition
(8
1
,
...
,8
m
)
of
{I,
...
,k}
and metric representations
for i
E {I,
...
,
m},
for which the obvious diagram commutes.
Theorem 20.1.1 is
an
essential result in the metric theory of graphs, which
has
many
applications;
we
will present a
number
of them, in particular, in Sec-
tions 20.2, 20.3
and
in
Chapter
21.
The
crucial tool for constructing the canonical
metric representation of a
graph
G is Djokovic's relation
(J,
introduced earlier in
(18.0.2).
The
factors
in
the canonical metric representation correspond, in fact,
to
the
equivalence classes of the transitive closure
(J*
of
(J.
Let us mention some
useful rules for computing them:
- Any two edges on
an
odd isometric circuit are in relation by
(J.
- Let C = (a1,
...
,
a2m)
be
an
isometric even circuit in G. Call the two edges
ei
:=
(ai,
ai+d
and
em+i
:=
(am+i' am+i+d (where the indices are taken modulo
m)
opposite on C
if
da(ai, am+i) = da(ai+1' am+i+d =
m.
Clearly,
if
ei
and
em+i are opposite
on
C,
then
ei
and
em+i
are
in
relation by
(J.
It
is observed in Lomonosov
and
Sebii
[1993]
that,
if
G is a
bipartite
graph,
then
two edges are in relation by
(J
if
and
only
if
they are opposite on some even circuit
ofG.
The
following lemma is crucial for the
proof
of Theorem 20.1.1.
Lemma
20.1.2.
Let E
1
,
...
,Ek
denote the equivalence classes
of
the transitive
closure
(J*
of
the relation
(J,
defined in relation (18.0.2). Given two nodes
a,
b
of
G, let P
be
a shortest path from a to
b,
and let Q
be
another path joining a to b
in
G. Then, for all h =
1,
...
,k,
Proof. Set P = (xo =
a,xl,
...
,xp
= b). For any index h E
{I,
...
,k}
and
any
node x of G, set
h(x)
:=
iE{
1,
...
,p
}I("'.-l ,,,,.)EEk
20.1 Canonical Metric
Representation
of
a
Graph
299
Hence,
h(a)
= IE(P) n
Ehl
and
h(b)
=
-IE(P)
n Ehl. Let (x,
y)
be
an
edge
of
G. We claim
Indeed,
h(x)
-
h(y)
=
is equal
to
0, since
the
edge (x, y) is
not
in
relation by
(J
with
any of
the
edges
of
Eh.
On
the
other
hand,
Ih(x)
- h(y)1 s 2 if (x,y) E
Eh·
Indeed, by
the
above
argument,
Ih(x)
-
fh(y)1
= I L (fJ(x) - fj(y))1
l~j~k
= I(dc(x,b) - dc(x,a)) - (dc(y,b) - dc(y,a))1
S Idc(x,
b)
- dc(x,
a)1
+ Idc(Y,
b)
- dc(y,
a)1
s
2.
As
h(a)
=
IE(p)nEhl
and
h(b)
=
-IE(p)nEhl,
when
moving along
the
nodes
of
the
path
Q,
the
function
h(.)
changes
in
absolute value by
2IE(p)nEhl.
But,
on
an
edge
of
E \
Eh,
the
function fh(.) remains unchanged
and,
on
an
edge of
Eh,
h(')
increases by
at
most
2.
This
implies
that
the
path
Q
must
contain
at
least
IE(P)
n
Ehl
edges from
Eh·
I
Proof of
Theorem
20.1.1. As
in
Lemma
20.1.2, let
El'
...
'
Ek
denote
the
equivalence classes
of
the
transitive closure
(J*
of
the
relation
(J.
For each h =
1,
...
,
k,
let
Gh denote
the
graph
obtained
from G by contracting
the
edges of
E \ E
h
•
In
other
words, for
constructing
G
h
,
one identifies any two nodes
of
G
that
are
joined
by a
path
containing no edge from E
h
.
This
defines a surjective
mapping
ah
from V(G)
to
V(G
h
)
and
a
mapping
a:
V(G)
---+
II
V(G
h
)
l~h~k
by
setting
a(v):=
(al(v),
...
,ak(v)) for each node v
ofG.
We show
that
the
mapping
a provides
the
required metric representation of G. For this,
we
have
to
check
that
a is
an
irredundant
isometric
embedding
and
that
each factor G
h
is irreducible. Take two nodes
a,
b of G
and
a
shortest
path
P from a
to
b
in
G.
We show
dc(a,b)=
L dCh(ah(a),ah(b)).
l~h~k
Indeed, for each
h,
dch(ah(a),ah(b)) is
the
minimum
value of IE(Q)
nEhl
taken
over all
paths
Q joining a
and
b;
hence, by
Lemma
20.1.2, dCh(ah(a),ah(b)) =
IE(P)
n Ehl. Therefore,
L dch(ah(a), ah(b)) = L IE(P) n
Ehl
= IE(P)I = dc(a,
b).
300
Chapter
20. Isometric
Embeddings
of
Graphs
into
Cartesian
Products
This
shows
that
cr
is
an
isometric embedding of G into
rr~=l
G
h
.
Moreover,
using again
Lemma
20.1.2,
the
endpoints
of
an
edge
of
Eh are
not
identified
when
constructing
G
h
.
Hence, each factor G
h
has
at
least two nodes. Therefore,
the
embedding
cr
is
irredundant
since
the
mappings
crh
are surjective. Consider
now
another
metric representation
of G
and
denote by
(Xl,
...
,x
m
)
the image of a node X
of
G.
If
e = (x,
y)
is
an
edge
of
G corresponding to
an
edge
in
the
j-th
factor H
j
, i.e., (Xj, yj) E
E(Hj)
and
Xi
=
Yi
for all i E {I,
...
,m}
\
{j},
then
each edge f
in
relation by
()
with
e
is
also
an
edge in
Hj.
Therefore, each factor H
j
"contains" exactly
the
edges
of
UiEJ
Ei
for some
nonempty
set J of indices.
In
particular,
m
~
k holds.
This
implies
that
each factor Gh is irreducible (else, one would have a metric
representation
of G
with
more
than
k factors). Therefore,
G'-+
G
I
X
...
X G
k
is
the
canonical metric representation of G.
This
concludes
the
proof. I
Corollary
20.1.3.
Let
G
be
a connected graph.
(i) G is irreducible
if
and
only
if
dimJ(G) = 1.
(ii)
If
G has n nodes,
then
dimJ(G)
~
n - 1, with equality
if
and
only
if
G is
a tree.
(iii) G embeds isometrically
into
(K3r
for
some
m
2:
1 'if
and
only
if
the
relation
()
'is
transitive.
(iv) G embeds
i.~ometrically
into
(K2r
for
some
m
2:
1
if
and
only
if
G is
bipart'ite
and
()
is transitive.
Proof.
(i) follows
immediately
from
Theorem
20,1.1.
(ii) Set k
:=
dimJ( G)
and
let T be a
spanning
tree in G. We claim
that
T
contains
at
least one edge from each equivalence class E
h
,
Indeed, if e is
an
edge
from
E\E(T)
belonging to
the
class Eh
then,
by
Lemma
20.1.2, T
must
contain
at
least one edge from Eh. Therefore, n - 1 = IE(T) I
2:
k holds.
If
there
are two
edges
e,
fEE
in
relation by
(),
let T be a spanning tree containing
both
e
and
f;
then,
k
~
n - 2 holds.
This
shows
that
equality k = n - 1 holds only if G is
a tree.
(iii) Note
that
G embeds isometrically into (K3)m if
and
only if each factor G
h
in
the
canonical representation of
Gis
K2
or
K3 (see
Remark
20.1.10).
On
the
other
hand,
G
h
is K2 or K3 if
and
only if Eh consists of all
the
edges
that
are
cut
by
the
partition
of V into
G(a,
b)
U G(b, a) U G=(a, b), where (a,
b)
E Eh, in
which case
()
is transitive.
The
assertion (iv) follows from (iii) since
G=(a,
b)
= 0 for each edge (a,
b)
when
G is
bipartite.
I
One
can
easily check
that,
for G
bipartite,
the
relation
()
is
transitive
if
and
only
if
G(a,
b)
is convex for all adjacent nodes a, b of G. Hence, Corol-
lary
20.1.3 (iv) implies
the
characterization
of
hypercube
embeddable
graphs
20.1 Canonical Metric
Representation
of a
Graph
301
stated
in
Theorem
19.1.1.
In
particular,
if G is hypercube
embeddable
with
isometric dimension
dimI(G)
=
k,
then
G
'--->
(K2)k is
the
canonical
metric
representation
of G. Lomonosov
and
SebCi
[1993]
give the following
additional
information.
Proposition
20.1.4.
If
G is a bipartite graph,
then
all the
factors
G
1
,
...
,Gk
of
its
canonical
metric
representation
are bipartite graphs.
Proof.
Suppose, for contradiction,
that
a factor
Gh
of
the
canonical
metric
representation
of G
is
not
bipartite.
Then,
there exists a circuit C of G such
that
IE(
C)
nEhl is odd. Choose such a circuit C of minimal length. As G is
bipartite,
C
has
even length, say C = (a1,a1,
...
,a2m)'
Consider
the
pairs
(ai,a
m
+;)
(where
the
indices are
taken
modulo
m)
of
diametrally
opposed nodes of
C.
If
dc(ai'
am+i) =
dc(ai+1'
am+i+1) =
m,
then
dc(am+i'
ai+1) -
dc(am+i'
ai) =
-1
and
dc(am+i+1'
ai+1)-dc(am+i+lJ
ai) =
1,
which implies
that
the
edges (ai,
ai+d
and
(am+i'
am+i+d
are
in
relation by
().
Hence, there exists a
pair
(ai, am+i) for
which
dc
( ai, a
m
+;) < m (otherwise,
any
two oposite edges
of
C are
in
relation
by
(),
implying
that
IE(
C)
n
Ehl
is even). Let P be a
shortest
path
from ai to
am+i
in
G. Suppose
that
only
the
endnodes of P are
on
C.
The
endnodes
of
P
partition
C into two
paths
which, together
with
P,
form two circuits C
1
and
C
2
•
As C
1
and
C
2
have smaller
length
than
C,
we
deduce
that
both
IE(C
1
)
n Ehl
and
IE(C
2
)
n Ehl are even.
This
implies
that
IE(C) n
Ehl
is even, yielding a
contradiction.
The
reasoning is
the
same
if P meets C
in
other
nodes
than
its
endnodes. I
Remark
20.1.5.
Let G be a
graph
on
n nodes
with
m edges.
Its
canonical
metric
representation
G
'--->
G
1
X
..•
X
Gk
can
be
found in polynomial time; more
precisely,
in
time
O(mn)
using O(m) space. Indeed,
it
can
be
obtained
in
the
following way:
(i)
Compute
the
relation
()
and
determine
the
equivalence classes E
1
,
...
,E
k
of
its
transitive closure ()*.
(ii) For each h =
1,
...
,k,
construct
the
graph
Gh
from G by contracting
the
edges of E \ E
h
.
Step
(ii)
can
be easily executed
in
time
O(nm)
using O(m) space. (Indeed, given
an
equivalence class
Eh,
the
graph
Gh
can
be
constructed
as follows: Delete
the
edges from
Eh
in
G
and
compute
the
connected components
in
the
resulting
graph;
they
are precisely
the
vertices of G
h
.
There
is
an
edge between two vertices
of
G h
if
there is
an
edge between
the
two corresponding components. Finally,
we
know from Corollary 20.1.3 (ii)
that
there are
at
most n - 1 equivalence
classes.)
Step
(i)
can
obviously
be
executed
in
O(m
2
)
time. Feder
[1992]
shows
how to execute
Step
(i)
in
O(mn)
time. For this, he considers
another
relation
(}1
contained
in
()
and
such
that
()
and
(}1
have
the
same transitive closure, i.e.,
()* =
(}i.
Namely, given a
spanning
tree
T
in
G, let
e
(}1
e'
{==:?
e
()
e'
and
Tn
{e,
e'}
-#
0.