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.

Definition

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

The cubicity of a graph $G$ , denoted by $\operatorname {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\geq 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$ .

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

Relations to certain graph classes, upper bound

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

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

For $n\in \mathbb {N} ^{*}$ , $\operatorname {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.

For $p\in \mathbb {N} ^{*}$ , $\operatorname {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, $\operatorname {cub} (G)\leq \lfloor 2n/3\rfloor$ . Moreover, this upper bound is best possible in terms of $n$ .

Relations to other graph dimensions

Relations to boxicity: bounds

The cubicity of a graph $G$ is closely related to its boxicity, denoted by $\operatorname {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., $~\operatorname {box} (G)\leq \operatorname {cub} (G).$

In the other direction, it can be shown that for a graph $G$ on $n$ vertices, $~\operatorname {cub} (G)\leq \lceil \log _{2}n\rceil \operatorname {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 $\operatorname {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: $~\operatorname {cub} (K_{1,5})=3>\operatorname {sph} (K_{1,5})=2.$

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

Notes

↑ Fishburn (1983, p. 309, Section 1)
↑ Roberts (1969, pp. 301–310)
↑ Chandran & Mathew (2009, p. 2, Section 1)
↑ Fishburn (1983, p. 309, Section 1)
↑ Roberts (1969, p. 302, Section 1) uses closed cubes of side-length $1$ .
Footnote 1 on p. 302: "Boxes are not necessarily closed, though it is not hard to show that if a representation [of $G$ ] is attainable with [open] boxes in $\mathrm {E} ^{k}$ , it is attainable with closed boxes in $\mathrm {E} ^{k}$ .".
↑ Chandran & Mathew (2009, p. 2, Section 1, Definition 4) use Cartesian products of closed intervals $[a_{i},a_{i}+1]$ .
↑ Fishburn (1983, p. 309, Section 1)
↑ Roberts (1969), pp. 302–303, Section 2.
↑ Chandran & Mathew (2009), p. 2, Section 1, Definition 4.
↑ Roberts (1969), p. 304, Section 3, Proof of Theorem 2.
1 2 3 Fishburn (1983), p. 310, Section 1.
↑ Roberts (1969), p. 303, Section 3, Theorem 1.
↑ Roberts (1969), p. 304, Section 3, Theorem 2.
↑ Roberts (1969), p. 306, Section 4, Theorem 5.
↑ Chandran & Mathew (2009, p. 3, Section 2, Theorem 1)
↑ Fishburn (1983, p. 309, Section 1)
↑ Fishburn (1983, pp. 310–318, Sections 2–3)

References

Chandran, L. Sunil; Mathew, K. Ashik (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
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
Roberts, Fred S. (1969), "On the boxicity and cubicity of a graph", in Tutte, W. T. (ed.), Recent Progress in Combinatorics (PDF), Academic Press, pp. 301–310, ISBN 978-0-12-705150-5

[1] Fishburn (1983, p. 309, Section 1)

[2] Roberts (1969, pp. 301–310)

[3] Chandran & Mathew (2009, p. 2, Section 1)

[4] Fishburn (1983, p. 309, Section 1)

[5] Roberts (1969, p. 302, Section 1) uses closed cubes of side-length $1$ .
Footnote 1 on p. 302: "Boxes are not necessarily closed, though it is not hard to show that if a representation [of $G$ ] is attainable with [open] boxes in $\mathrm {E} ^{k}$ , it is attainable with closed boxes in $\mathrm {E} ^{k}$ .".

[6] Chandran & Mathew (2009, p. 2, Section 1, Definition 4) use Cartesian products of closed intervals $[a_{i},a_{i}+1]$ .

[7] Fishburn (1983, p. 309, Section 1)

[FOOTNOTERoberts1969302–303Section_2-8] Roberts (1969), pp. 302–303, Section 2.

[FOOTNOTEChandranMathew20092Section_1,_Definition_4-9] Chandran & Mathew (2009), p. 2, Section 1, Definition 4.

[FOOTNOTERoberts1969304Section_3,_Proof_of_Theorem_2-10] Roberts (1969), p. 304, Section 3, Proof of Theorem 2.

[FOOTNOTEFishburn1983310Section_1-11] 1 2 3 Fishburn (1983), p. 310, Section 1.

[FOOTNOTERoberts1969303Section_3,_Theorem_1-12] Roberts (1969), p. 303, Section 3, Theorem 1.

[FOOTNOTERoberts1969304Section_3,_Theorem_2-13] Roberts (1969), p. 304, Section 3, Theorem 2.

[FOOTNOTERoberts1969306Section_4,_Theorem_5-14] Roberts (1969), p. 306, Section 4, Theorem 5.

[15] Chandran & Mathew (2009, p. 3, Section 2, Theorem 1)

[16] Fishburn (1983, p. 309, Section 1)

[17] Fishburn (1983, pp. 310–318, Sections 2–3)