Cubicity

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 1, realized as the intersection graph of unit 1-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 realized as the intersection graph of axis-parallel closed unit $k$-cubes in $k$-dimensional Euclidean space.

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

Relations to certain graph classes, bounds

For a graph $G,\mathrm{cub}(G)=0$ iff $G$ is complete.

For $n\in {\mathbb{\mathbb{N}}}^{*},\mathrm{cub}(K_{1,n})=\lfloor {\log }_2(2n-1)\rfloor ,$ where $K_{1,n}$ denotes the star graph of ($1$ center and) $n$ vertices, and $\lfloor \cdot \rfloor$ denotes the floor function.

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

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$.

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, 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 $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.

References

• Chandran, L. Sunil; Mathew, K. Ashik (2009-04-28), "An upper bound for Cubicity in terms of Boxicity" (in en), Discrete Mathematics 309 (8): 2571–2574, doi:10.1016/j.disc.2008.04.011, ISSN 0012-365X, https://www.sciencedirect.com/science/article/pii/S0012365X08002240 
• Fishburn, Peter C. (1983-12-01), "On the sphericity and cubicity of graphs" (in en), Journal of Combinatorial Theory, Series B 35 (3): 309–318, doi:10.1016/0095-8956(83)90057-6, ISSN 0095-8956, https://dx.doi.org/10.1016/0095-8956%2883%2990057-6 
• Roberts, Fred S. (1969), "On the boxicity and cubicity of a graph", in Tutte, W. T., Recent Progress in Combinatorics, Academic Press, pp. 301–310, ISBN 978-0-12-705150-5, https://dn721806.ca.archive.org/0/items/boxicity/boxicity.pdf