On the Boxicity and Cubicity of Hypercubes

Details On the Boxicity and Cubicity of Hypercubes On the Boxicity and Cubicity of Hypercubes

2006-05-10

arxiv.org/abs/math/0605246v1

Mathematics

Combinatorics

Scientific paper

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) = \Theta(\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.

Affiliated with

Also associated with

No associations

Rating

On the Boxicity and Cubicity of Hypercubes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Boxicity and Cubicity of Hypercubes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Boxicity and Cubicity of Hypercubes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-705863