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.
Definition 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 represented as the intersection graph of axis-parallel closed unit -cubes in -dimensional Euclidean space, . uses closed cubes of side-length .Footnote 1 on p. 302: "Boxes are not necessarily closed, though it is not hard to show that if a representation [of ] is attainable with [open] boxes in , it is attainable with closed boxes in .". use Cartesian products of closed intervals .
For , a graph can have such a representation in if and only if is the intersection of indifference graphs on the same vertex set as .
The cubicity of a complete graph is defined to be zero.
Relations to certain graph classes, upper bound For a graph , if and only if is complete.
For a graph , if and only if is a unit interval graph that is not complete.
For , , where denotes the star graph, a tree with one internal vertex and leaves, and where 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 .
Relations to other graph dimensions Relations to boxicity: bounds 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, but with axis-parallel boxes instead of axis-parallel unit cubes.
Since a cube is a special case of a box, the cubicity of a graph is always an upper bound for its boxicity, i.e.,
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.
Relations to sphericity The sphericity of a graph denoted by is defined in the same way as cubicity but with congruent spheres instead of axis-parallel unit cubes.
For certain graphs, cubicity exceeds sphericity; the five-pointed star, is an example:
In the other direction, graphs can be constructed so that for
Notes
References