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