2008/10/15 by L. Sunil Chandran, Chandran, L. Sunil, Anita Das +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Graph theory and applications #cs.DM
paper · pdf · doi:10.48550/arxiv.0810.2697
7 pages
arxiv created 2008/10/15 · openalex publication_date 2008/10/15 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
\it A unit cube in k-dimension (or a k-cube) is defined as the cartesian product R1 × R2 × ... × Rk, where each Ri is a closed interval on the real line of the form [ai, ai+1]. The \it cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. Many NP-complete graph problems can be solved efficiently or have good approximation ratios in graphs of low cubicity. In most of these cases the first step is to get a low dimensional cube representation of the given graph. It is known that for a graph G, cub(G) ≤ \lfloor(2n)/(3)\rfloor. Recently it has been shown that for a graph G, cub(G) ≤ 4(Δ+ 1)ln n, where n and Δ are the number of vertices and maximum degree of G, respectively. In this paper, we show that for a bipartite graph G = (A ∪ B, E) with |A| = n1, |B| = n2, n1 ≤ n2, and Δ' = min\ΔA, ΔB\, where ΔA = maxa ∈ Ad(a) and ΔB = maxb ∈ Bd(b), d(a) and d(b) being the degree of a and b in G respectively, cub(G) ≤ 2(Δ'+2) \lceil ln n2 \rceil. We also give an efficient randomized algorithm to construct the cube representation of G in 3(Δ'+2)\lceil ln n2 \rceil dimensions. The reader may note that in general Δ' can be much smaller than Δ.