The cubicity of hypercube graphs

Abstract: For a graph , its cubicity is the minimum dimension such that is representable as the intersection graph of (axis-parallel) cubes in -dimensional space. (A -dimensional cube is a Cartesian product , where is a closed interval of the form on the real line.) Chandran et al. [L.S. Chandran, C. Mannino, G. Oriolo, On the cubicity of certain graphs, Information Processing Letters 94 (2005) 113–118] showed that for a -dimensional hypercube , . In this paper, we use the probabilistic method to show that . The parameter boxicity generalizes cubicity: the boxicity of a graph is defined as the minimum dimension such that is representable as the intersection graph of axis-parallel boxes in -dimensional space. Since for any graph , our result implies that . The problem of determining a non-trivial lower bound for is left open. [Copyright &y& Elsevier]