Article View: comp.hypercube
Article #83Hypercube Embedding
From: pase
Date: Tue, 27 Oct 1987 15:56
Date: Tue, 27 Oct 1987 15:56
15 lines
1136 bytes
1136 bytes
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
Technical Details
Message-ID:
<599@hubcap.UUCP>Path:
arc1-ca.pugleaf.net!utzoo!mnetor!uunet!husc6!bloom-beacon!gatech!hubcap!ogcvax!paseShow Full Headers
Complete Article Headers
Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: arc1-ca.pugleaf.net!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?