Cubicity
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/aa/A_graph_with_cubicity_2.svg/260px-A_graph_with_cubicity_2.svg.png)
In graph theory, cubicity is a graph invariant defined to be the smallest dimension such that a graph can be realized as an intersection graph of 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 an intersection graph of axis-parallel rectangles in Euclidean space.[1]
Definition
Let be a graph. Then the cubicity of , denoted by , is the smallest integer such that can be realized as an intersection graph of axis-parallel unit cubes in -dimensional Euclidean space.[2]
The cubicity of a graph is closely related to the boxicity of a graph, denoted . The definition of boxicity is essentially the same as cubicity, except in terms of using axis-parallel rectangles instead of cubes. Since a cube is a special case of a rectangle, the cubicity of a graph is always an upper bound for the boxicity of a graph. In the other direction, it can be shown that for any graph on vertices, the inequality , where is the ceiling function, i.e., the smallest integer greater than or equal to .[3]
References
- ^ Roberts, F. S. (1969). On the boxicity and cubicity of a graph. In W. T. Tutte (Ed.), Recent Progress in Combinatorics (pp. 301–310). San Diego, CA: Academic Press. ISBN 978-0-12-705150-5
- ^ Fishburn, Peter C (1983-12-01). "On the sphericity and cubicity of graphs". Journal of Combinatorial Theory, Series B. 35 (3): 309–318. doi:10.1016/0095-8956(83)90057-6. ISSN 0095-8956.
- ^ Sunil Chandran, L.; Ashik Mathew, K. (2009-04-28). "An upper bound for Cubicity in terms of Boxicity". Discrete Mathematics. 309 (8): 2571–2574. arXiv:math/0605486. doi:10.1016/j.disc.2008.04.011. ISSN 0012-365X. S2CID 7837544.