🚀 go-pugleaf

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