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]

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

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

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

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

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

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

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

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

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

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

In the other direction, it can be shown that for a graph G {\displaystyle G} on n {\displaystyle n} vertices,   cub ⁡ ( G ) ≤ ⌈ log 2 ⁡ n ⌉ box ⁡ ( G ) ,   {\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 G , {\displaystyle G,} denoted by sph ⁡ ( G ) , {\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, K 1 , 5 , {\displaystyle K_{1,5},} is an example:   cub ⁡ ( K 1 , 5 ) = 3 > sph ⁡ ( K 1 , 5 ) = 2. {\displaystyle ~\operatorname {cub} (K_{1,5})=3>\operatorname {sph} (K_{1,5})=2.} ^[19]

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