Cubicity

A graph with cubicity Template:Math, realized as the intersection graph of axis-parallel unit Template:Math-cubes, i.e. axis-parallel unit squares, in the plane.

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.

An indifference graph with cubicity Template:Math, realized as the intersection graph of unit Template:Math-cubes, i.e. unit intervals, on the real number line.

Definition

This article only considers simple, undirected graphs, with finite and non-empty vertex sets.

The cubicity of a graph $G$, denoted by $\mathrm{cub}(G)$, is the smallest integer $k$ such that $G$ can be represented as the intersection graph of axis-parallel closed unit $k$-cubes in $k$-dimensional Euclidean space, ${\mathrm{E}}^k$.

For $k\ge 1$, a graph $G$ can have such a representation in ${\mathrm{E}}^k$ if and only if $G$ is the intersection of $k$ indifference graphs on the same vertex set as $G$.Template:Sfnp

The cubicity of a complete graph is defined to be zero.Template:Sfnp

Relations to certain graph classes, upper bound

For a graph $G$, $\mathrm{cub}(G)=0$ if and only if $G$ is complete.Template:Sfnp

For a graph $G$, $\mathrm{cub}(G)=1$ if and only if $G$ is a unit interval graph that is not complete.Template:Sfnp

For $n\in {\mathbb{N}}^{\ast }$, $\mathrm{cub}(K_{1,n})=\lfloor {\log }_2(2n-1)\rfloor$, where $K_{1,n}$ denotes the star graph, a tree with one internal vertex and $n$ leaves, and where $\lfloor \cdot \rfloor$ denotes the floor function.Template:Sfnp

For $p\in {\mathbb{N}}^{\ast }$, $\mathrm{cub}(K_{p(2)})=p$, where $K_{p(2)}$ denotes the complete multipartite graph with $p$ parts of cardinal $2$.Template:SfnpTemplate:Sfnp

For a graph $G$ on $n$ vertices, $\mathrm{cub}(G)\le \lfloor 2n/3\rfloor$. Moreover, this upper bound is best possible in terms of $n$.Template:SfnpTemplate:Sfnp

Relations to other graph dimensions

Relations to boxicity: bounds

The cubicity of a graph $G$ is closely related to its boxicity, denoted by $\mathrm{box}(G).$ 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 $G$ is always an upper bound for its boxicity, i.e., $\mathrm{box}(G)\le \mathrm{cub}(G).$

In the other direction, it can be shown that for a graph $G$ on $n$ vertices, $\mathrm{cub}(G)\le \lceil {\log }_{2}n\rceil \mathrm{box}(G),$ where $\lceil \cdot \rceil$ denotes the ceiling function. Moreover, this upper bound is tight.

Relations to sphericity

The sphericity of a graph $G,$ denoted by $\mathrm{sph}(G),$ 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, $K_{1,5},$ is an example: $\mathrm{cub}(K_{1,5})=3>\mathrm{sph}(K_{1,5})=2.$

In the other direction, graphs $G$ can be constructed so that $\mathrm{sph}(G)>\mathrm{cub}(G)=k,$ for $k\in \{2,3\}.$

References

• Template:Citation
• Template:Citation
• Template:Citation