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.^[1] 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.^[2]

Definition

This article only considers simple, undirected graphs, with finite and non-empty vertex sets.^[3]^[4]

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}$ .^[5]^[6]^[7]

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$ .^[8]

The cubicity of a complete graph is defined to be zero.^[9]

Relations to certain graph classes, upper bound

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

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

For $n\in \mathbb {N} ^{*}\!,~\operatorname {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.^[12]^[13]

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$ .^[14]^[15]

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$ .^[16]^[17]

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.^[18]

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.$ ^[19]

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

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)
Indeed: $\forall ~u,v\in \mathrm {V} (G),$ $\{u,v\}\in \mathrm {E} (G)$ iff $\|f(u)-f(v)\|_{\infty }\leq 1,$ iff $~\forall ~1\leq i\leq k,~|f_{i}(u)-f_{i}(v)|\leq 1,~$ i.e., $~\{u,v\}\in \mathrm {E} (G_{i}).$
And so: $\forall ~u,w\in \mathrm {V} (G),$ $\{u,w\}\notin \mathrm {E} (G)$ iff $\|f(u)-f(w)\|_{\infty }>1,$ iff $~\exists ~1\leq i\leq k~$ such that $~|f_{i}(u)-f_{i}(w)|>1,~$ i.e., $~\{u,w\}\notin \mathrm {E} (G_{i});$
but $~\forall ~1\leq j\neq i\leq k,~|f_{j}(u)-f_{j}(w)|$ may be $\leq 1,~$ i.e., $~\{u,w\}$ may $\in \mathrm {E} (G_{j}).$
↑ Chandran & Mathew (2009, p. 2, Section 1, Definition 4)
↑ Roberts (1969, p. 304, Section 3, Proof of Theorem 2)
↑ Fishburn (1983, p. 310, Section 1)
↑ Roberts (1969, p. 303, Section 3, Theorem 1)
↑ That is, cub(K_1,n) = ⌈log₂(n)⌉. Proof: ∀ n ∈ ℕ*, 1 ≤ n; so, 0 < n ≤ 2n−1. ∀ n ∈ ℕ*, ∃! c ∈ ℕ such that n ≤ 2ᶜ ≤ 2n−1 (namely, c is the least k ∈ ℕ such that n ≤ 2ᵏ); so, ∃! c ∈ ℕ such that log₂(n) ≤ c ≤ log₂(2n−1). So, ⌈log₂(n)⌉ = c = ⌊log₂(2n−1)⌋.
↑ Fishburn (1983, p. 310, Section 1)
↑ Roberts (1969, p. 304, Section 3, Theorem 2)
↑ Fishburn (1983, p. 310, Section 1)
↑ 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)