On the sphericity and cubicity of graphs

The sphericity of a graph G is the smallest n such that the vertices in G can be mapped into unit-diameter spheres in n-space in such a way that two vertices are adjacent in G if and only if their assigned spheres intersect. The cubicity of G is defined similarly with unit cubes (edges parallel to the axes) used instead of unitdiameter spheres. In his study of molecular conformation, Havel (Ph.D. dissertation, Univ. of Calif., Berkeley, 1982) showed that there are finite graphs of sphericity 2 that have arbitrarily large cubicity, but he left open the question of whether there are graphs with sphericity greater than cubicity. It is shown here that such graphs exist for cubicity 2 or 3. The construction used to prove this generalizes to larger values for cubicity, but the proof technique does not. Hence it remains open whether there are graphs with large cubicities whose sphericities exceed their cubicities.