Cubicity 📖 Wikipedia

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]

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

The cubicity of a graph ${\displaystyle G}$, denoted by ${\displaystyle \operatorname {cub} (G)}$, is the smallest integer ${\displaystyle k}$ such that ${\displaystyle G}$ can be represented as the intersection graph of axis-parallel closed unit ${\displaystyle k}$-cubes in ${\displaystyle k}$-dimensional Euclidean space, ${\displaystyle \mathrm {E} ^{k}}$.^[5][6][7]

For ${\displaystyle k\geq 1}$, a graph ${\displaystyle G}$ can have such a representation in ${\displaystyle \mathrm {E} ^{k}}$ if and only if ${\displaystyle G}$ is the intersection of ${\displaystyle k}$ indifference graphs on the same vertex set as ${\displaystyle G}$.^[8]

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

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

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

For ${\displaystyle n\in \mathbb {N} ^{*}\!,~\operatorname {cub} (K_{1,n})=\lfloor \log _{2}(2n-1)\rfloor ,~}$ where ${\displaystyle K_{1,n}}$ denotes the star graph of (${\displaystyle 1}$ center and) ${\displaystyle n}$ vertices, and ${\displaystyle \lfloor \cdot \rfloor }$ denotes the floor function.^[12][13]

For ${\displaystyle p\in \mathbb {N} ^{*}\!,~\operatorname {cub} (K_{p(2)})=p,~}$ where ${\displaystyle K_{p(2)}}$ denotes the complete multipartite graph with ${\displaystyle p}$ parts of cardinal ${\displaystyle 2}$.^[14][15]

For a graph ${\displaystyle G}$ on ${\displaystyle n}$ vertices, ${\displaystyle ~\operatorname {cub} (G)\leq \lfloor 2n/3\rfloor .~}$ Moreover, this upper bound is best possible in terms of ${\displaystyle n}$.^[16][17]

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

In the other direction, it can be shown that for a graph ${\displaystyle G}$ on ${\displaystyle n}$ vertices, ${\displaystyle ~\operatorname {cub} (G)\leq \lceil \log _{2}n\rceil \operatorname {box} (G),~}$ where ${\displaystyle \lceil \cdot \rceil }$ denotes the ceiling function. Moreover, this upper bound is tight.^[18]

The sphericity of a graph ${\displaystyle G,}$ denoted by ${\displaystyle \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, ${\displaystyle K_{1,5},}$ is an example: ${\displaystyle ~\operatorname {cub} (K_{1,5})=3>\operatorname {sph} (K_{1,5})=2.}$^[19]

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