Cubicity

A graph with cubicity 2, realized as the intersection graph of axis-parallel unit 2-cubes, i.e. axis-parallel unit squares, in the plane.

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]

An indifference graph with cubicity 1, realized as the intersection graph of unit 1-cubes, i.e. unit intervals, on the real number line.

Definition

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]

Relations to certain graph classes, bounds

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

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. ^{[11] [12]}

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}$. ^{[13] [14]}

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}$. ^{[15] [16]}

Relations to other graph dimensions

Relations to boxicity: bounds

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, except in terms of using axis-parallel rectangles instead of axis-parallel unit cubes.

Since a cube is a special case of a rectangle, 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. ^[17]

Relations to sphericity

The sphericity of a graph ${\displaystyle G}$ is denoted by ${\displaystyle \operatorname {sph} (G).}$

There exist graphs ${\displaystyle G}$ for which ${\displaystyle ~\operatorname {cub} (G)>\operatorname {sph} (G);~}$ the five-pointed star is an example: ${\displaystyle ~\operatorname {cub} (K_{1,5})=3>\operatorname {sph} (K_{1,5})=2.}$ ^[18]

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

Notes

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 ${\displaystyle 1}$.
   Footnote 1 on p. 302: "Boxes are not necessarily closed, though it is not hard to show that if a representation [of ${\displaystyle G}$] is attainable with [open] boxes in ${\displaystyle \mathrm {E} ^{k}}$, it is attainable with closed boxes in ${\displaystyle \mathrm {E} ^{k}}$.".
6. Chandran & Mathew (2009 , p. 2, Section 1, Definition 4) use Cartesian products of closed intervals ${\displaystyle [a_{i},a_{i}+1]}$.
7. Fishburn (1983 , p. 309, Section 1)
8. Roberts (1969 , pp. 302–303, Section 2)
   Indeed: ${\displaystyle \forall ~u,v\in \mathrm {V} (G),}$${\displaystyle \{u,v\}\in \mathrm {E} (G)}$ iff ${\displaystyle \|f(u)-f(v)\|_{\infty }\leq 1,}$iff ${\displaystyle ~\forall ~1\leq i\leq k,~|f_{i}(u)-f_{i}(v)|\leq 1,~}$i.e., ${\displaystyle ~\{u,v\}\in \mathrm {E} (G_{i}).}$
   And so: ${\displaystyle \forall ~u,w\in \mathrm {V} (G),}$${\displaystyle \{u,w\}\notin \mathrm {E} (G)}$ iff ${\displaystyle \|f(u)-f(w)\|_{\infty }>1,}$iff ${\displaystyle ~\exists ~1\leq i\leq k~}$ such that ${\displaystyle ~|f_{i}(u)-f_{i}(w)|>1,~}$i.e., ${\displaystyle ~\{u,w\}\notin \mathrm {E} (G_{i});}$
   but ${\displaystyle ~\forall ~1\leq j\neq i\leq k,~|f_{j}(u)-f_{j}(w)|}$ may be ${\displaystyle \leq 1,~}$i.e., ${\displaystyle ~\{u,w\}}$ may ${\displaystyle \in \mathrm {E} (G_{j}).}$
9. Chandran & Mathew (2009 , p. 2, Section 1, Definition 4)
10. Roberts (1969 , p. 304, Section 3, Proof of Theorem 2)
11. Roberts (1969 , p. 303, Section 3, Theorem 1)
12. 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)⌋.
13. Fishburn (1983 , p. 310, Section 1)
14. Roberts (1969 , p. 304, Section 3, Theorem 2)
15. Fishburn (1983 , p. 310, Section 1)
16. Roberts (1969 , p. 306, Section 4, Theorem 5)
17. Chandran & Mathew (2009 , p. 3, Section 2, Theorem 1)
18. Fishburn (1983 , p. 309, Section 1)
19. 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