An upper bound for Cubicity in terms of Boxicity
| dc.creator | Chandran, L. Sunil | |
| dc.creator | Mathew, K. Ashik | |
| dc.date | 2006-05-17 | |
| dc.date.accessioned | 2026-07-07T07:14:21Z | |
| dc.date.available | 2026-07-07T07:14:21Z | |
| dc.description | 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. | |
| dc.description | 6 pages, 0 figures | |
| dc.identifier | https://arxiv.org/abs/math/0605486 | |
| dc.identifier | http://arxiv.org/abs/math/0605486 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/112842 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C62 | |
| dc.title | An upper bound for Cubicity in terms of Boxicity | |
| dc.type | text |