From: yerman@vespucci.advicom.net (Niall Graham)
Subject: Re: Subgraphs of Hypercubs
Date: 30 Mar 1999 22:27:17 -0600
Newsgroups: sci.math.research
Keywords: What graphs embed in a k-cube?


   In particular, I wonder if any sufficient success in the following open
   problem has been made:
   ---------------------------------------------------------------------------
   A graph G is embeddable in a graph H if G is isomorphic to a subgraph of H.
   Characterise the graphs embeddable in the k-cube.
   ---------------------------------------------------------------------------

   This problem is listed in Bondy and Murty and in accordance with page of
   Stephen C. Locke at http://www.math.fau.edu/locke/unsolved.htm it's steel
   unsolved

   I would really appreciate also any information and references on connected
   problems/researches.

The cubical dimension of a graph G is the least n such that 
G is a subgraph of Q_n   (the n-cube).

The decision problem of determining if the cubical dimension of a graph
G is at most k was shown to be  NP-complete in

the complexity of cubical graphs , Information and Computation 66 (1985)
Afrati, Papadimitriou, Papageorgiou.

Niall Graham