Cubicity
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 [math]\displaystyle{ G }[/math] be a graph. Then the cubicity of [math]\displaystyle{ G }[/math], denoted by [math]\displaystyle{ \operatorname{cub} (G) }[/math], is the smallest integer [math]\displaystyle{ n }[/math] such that [math]\displaystyle{ G }[/math] can be realized as an intersection graph of axis-parallel unit cubes in [math]\displaystyle{ n }[/math]-dimensional Euclidean space.[2]
The cubicity of a graph is closely related to the boxicity of a graph, denoted [math]\displaystyle{ \operatorname{box} (G) }[/math]. 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 [math]\displaystyle{ G }[/math] on [math]\displaystyle{ m }[/math] vertices, the inequality [math]\displaystyle{ \operatorname{cub} (G) \leq \lceil \log_2 n \rceil \operatorname{box} (G) }[/math], where [math]\displaystyle{ \lceil x \rceil }[/math] is the ceiling function, i.e., the smallest integer greater than or equal to [math]\displaystyle{ x }[/math].[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" (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.
- ↑ Sunil Chandran, L.; Ashik Mathew, K. (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.
 |  |
