In the mathematical field of graph theory, cubicity is a graph invariant defined to be the smallest dimension such that a graph can be realized as the intersection graph of axis-parallel unit cubes in Euclidean space. Cubicity was introduced by Fred S. Roberts in 1969, along with a related invariant called boxicity that considers the smallest dimension needed to represent a graph as the intersection graph of axis-parallel rectangles in Euclidean space.
This article only considers simple, undirected graphs, with finite and non-empty vertex sets.
The cubicity of a graph , denoted by , is the smallest integer such that can be realized as the intersection graph of axis-parallel closed unit -cubes in -dimensional Euclidean space.
The cubicity of a complete graph is defined to be zero.
For a graph iff is complete.
For where denotes the star graph of ( center and) vertices, and denotes the floor function.
For where denotes the complete multipartite graph with parts of cardinal .
For a graph on vertices, Moreover, this upper bound is best possible in terms of .
The cubicity of a graph is closely related to its boxicity, denoted by . The definition of boxicity is essentially the same as that of cubicity, except in terms of using axis-parallel rectangles instead of axis-parallel unit cubes. Since a cube is a special case of a rectangle, the cubicity of a graph is always an upper bound for its boxicity, i.e., <br>In the other direction, it can be shown that for a graph on vertices, where denotes the ceiling function. Moreover, this upper bound is tight.