Cubicity

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]