{
  "id": "math/0605486",
  "version": "v1",
  "published": "2006-05-17T16:33:36.000Z",
  "updated": "2006-05-17T16:33:36.000Z",
  "title": "An upper bound for Cubicity in terms of Boxicity",
  "authors": [
    "L. Sunil Chandran",
    "K. Ashik Mathew"
  ],
  "comment": "6 pages, 0 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2006-05-17T16:33:36.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C62"
    ],
    "keywords": [
      "upper bound",
      "real line",
      "axis parallel b-dimensional boxes",
      "cartesian product",
      "closed interval"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2006math......5486C"
    }
  }
}