Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!bloom-beacon!gatech!hubcap!ogcvax!pase
From: pase@ogcvax.UUCP
Newsgroups: comp.hypercube,sci.math
Subject: Hypercube Embedding
Message-ID: <599@hubcap.UUCP>
Date: Tue, 27-Oct-87 10:56:29 EST
Article-I.D.: hubcap.599
Posted: Tue Oct 27 10:56:29 1987
Date-Received: Thu, 29-Oct-87 22:26:17 EST
Sender: fpst@hubcap.UUCP
Lines: 15
Approved: hypercube@hubcap.clemson.edu
Summary: What does graph embedding mean?
Xref: mnetor comp.hypercube:110 sci.math:2314

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