On the cubicity of enhanced hypercube

An axis-parallel k-dimension box is a Cartesian product R₁ × R₂ × ... × R_k, where each R_i is a closed interval of the form [a_i, b_i] on the real line. For a graph G, its boxicity(denoted by box(G)) is the minimum dimension k such that G is representable as the intersection graph of axis-parallel k-dimension boxes. Let each R_i be of the same length, then the k-dimension box is a k-dimension cube. When the boxes are restricted to be axis-parallel k-dimension cubes, the minimum k required to represent G is called the cubicity of G(denoted by cub(G)). Unit-interval graphs are graphs which can be representable as the intersection graph of intervals of length 1 on the real line. In this paper, we define a special unit-interval graph IG[X, Y], then we construct 2n such graphs which are defined on the vertex set V(Q_n,k), where Q_n,k is the enhanced hypercube. Because of the special structure of IG[X, Y], we get an upper bound for the cubicity of enhanced hypercube.