Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!cbosgd!ihnp4!homxb!mtuxo!mtune!rutgers!husc6!bloom-beacon!gatech!hubcap!rabaeza
From: rabaeza@hubcap.UUCP
Newsgroups: comp.hypercube,sci.math
Subject: Re: Hypercube Embedding
Message-ID: <614@hubcap.UUCP>
Date: Fri, 30-Oct-87 08:09:42 EST
Article-I.D.: hubcap.614
Posted: Fri Oct 30 08:09:42 1987
Date-Received: Sat, 31-Oct-87 20:07:32 EST
Sender: fpst@hubcap.UUCP
Lines: 35
Approved: hypercube@hubcap.clemson.edu
Xref: utgpu comp.hypercube:101 sci.math:2216

In article <599@hubcap.UUCP> ogcvax!pase@uunet.uu.net (Douglas M. Pase) writes:
>What does it mean to show a graph G is a subgraph of a hypercube?
>I see two possibilities:
>
>	1)  Both nodes and edges of G must map one-to-one such that
>	    the connectedness remains the same.
>
>	2)  Groups of connected nodes in G may be mapped to a single
>	    node of a hypercube such that the new graph G' which results
>	    is a hypercube.
>
>The problem of hypercube embedding is NP-complete, I'm just trying to figure
>out exactly what embedding means.  If I had to guess, I would say #1.  Would
>someone who knows please respond?
>--
>Doug Pase   --   ...ucbvax!tektronix!ogcvax!pase  or  pase@cse.ogc.edu.csnet

An embedding is a one-to-one mapping. For example a n-level complete binary
tree is embeddable in a hypercube of size 2^(n+2) and is not embeddable in
one of size 2^(n+1).

More general embeddings of a graph in the hypercube (or other graph)
are characterized by 3 parameters: expansion (number of
nodes of the hypercube over the number of vertices in the graph), dilation
(maximum stretching of an edge of the graph in the hypercube -for example
the one-to-one embedding has dilation 1), and load factor (maximum number of
edged mapped to a single edge of the hypercube). For example, is possible to
embed a n-level complete binary tree in a hypercube of size 2^(n+1)
(expansion is 2) with dilation 2.

Ricardo 
--
rabaeza@waterloo.csnet         1-519-885-1211 x6709    Ricardo Baeza-Yates
rabaeza%waterloo@csnet-relay.arpa                      CS Dept., U. Waterloo 
{allegra,decvax,ihnp4,utzoo}!watmath!watmum!rabaeza    Waterloo, Ont. N2L3G1