On the sphericity and cubicity of graphs (Q789416)

The cubicity of a graph G is the smallest n such that the vertices in G can be mapped into closed unit cubes (edges parallel to the axes) in n- space so that two vertices are adjacent in G if and only if their assigned spheres intersect. The sphericity of G is defined similarly using closed unit spheres instead of cubes. It was shown in [\textit{F. S. Roberts}, Recent Progress Combin., Proc. 3rd Waterloo Conf. 1968, 301-310 (1969; Zbl 0193.243)] that the cubicity of the complete N-partite graph \(K_{2,...,2}\) is N, and in [\textit{T. F. Havel,} Ph.D. dissertation, Berkeley (1982, p. 234) see also Congr. Numerantium 35, 361-371 (1982; Zbl 0516.05060)] that the sphericity of the same graph is 2 when \(N\geq 2\), so that cubicity can be arbitrarily larger than sphericity. In the reviewed paper, the question of whether a graph's sphericity can exceed its cubicity is answered in the affirmative: for each of \(n=2,3\), a family of graphs with cubicity n is constructed and it is shown that the sphericity of these graphs must exceed n. The actual values of the sphericities are not calculated; so it is left open whether sphericity can significantly exceed cubicity. It is also left open whether there exist graphs of cubicity \(n\geq 4\) whose sphericity exceeds n, and it is shown that the proof technique used for \(n=2\) and \(n=3\) breaks down for \(n\geq 5\).