On the Boxicity and Cubicity of Hypercubes
| dc.creator | Chandran, L. Sunil | |
| dc.creator | Sivadasan, Naveen | |
| dc.date | 2006-05-10 | |
| dc.date.accessioned | 2026-07-07T07:14:04Z | |
| dc.date.available | 2026-07-07T07:14:04Z | |
| dc.description | For a graph $G$, its \emph{cubicity} $cub(G)$ is the minimum dimension $k$ such that $G$ is representable as the intersection graph of (axis--parallel) cubes in $k$--dimensional space. Chandran, Mannino and Oriolo showed that for a $d$--dimensional hypercube $H_d$, $\frac{d-1}{\log d} \le cub(H_d) \le 2d$. In this paper, we show that $cub(H_d) = Θ(\frac{d}{\log d})$.The parameter \emph{boxicity} generalizes cubicity: the boxicity $box(G)$ of a graph $G$ is defined as the minimum dimension $k$ such that $G$ is representable as the intersection graph of axis parallel boxes in $k$ dimensional space. Since $box(G) \le cub(G)$ for any graph $G$, our result implies that $box(H_d) = O(\frac{d}{\log d})$. The problem of determining a non-trivial lower bound for $box(H_d)$ is left open. | |
| dc.identifier | https://arxiv.org/abs/math/0605246 | |
| dc.identifier | http://arxiv.org/abs/math/0605246 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/112722 | |
| dc.subject | Combinatorics | |
| dc.title | On the Boxicity and Cubicity of Hypercubes | |
| dc.type | text |