An upper bound for Cubicity in terms of Boxicity

Details An upper bound for Cubicity in terms of Boxicity An upper bound for Cubicity in terms of Boxicity

2006-05-17

arxiv.org/abs/math/0605486v1

Mathematics

Combinatorics

6 pages, 0 figures

Scientific paper

An axis-parallel b-dimensional box is a Cartesian product $R_1 \times R_2 \times ... \times R_b$ where each $R_i$ (for $1 \leq i \leq b$) is a closed interval of the form $[a_i,b_i]$ on the real line. The boxicity of any graph $G$, box(G) is the minimum positive integer b such that G can be represented as the intersection graph of axis parallel b-dimensional boxes. A b-dimensional cube is a Cartesian product $R_1 \times R_2\times ... \times R_b$, where each $R_i$ (for $1 \leq i \leq b$) is a closed interval of the form [$a_i$,$a_i$+1] on the real line. When the boxes are restricted to be axis-parallel cubes in b-dimension, the minimum dimension b required to represent the graph is called the cubicity of the graph (denoted by cub(G)). In this paper we prove that $cub(G)\leq \lceil \log n \rceil \boxi(G)$} where n is the number of vertices in the graph. This upper bound is tight.

Affiliated with

Also associated with

No associations

Rating

An upper bound for Cubicity in terms of Boxicity 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 An upper bound for Cubicity in terms of Boxicity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An upper bound for Cubicity in terms of Boxicity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-489991