On the cubicity of bipartite graphs
| dc.creator | Chandran, L. Sunil | |
| dc.creator | Das, Anita | |
| dc.creator | Sivadasan, Naveen | |
| dc.date | 2008-10-15 | |
| dc.date.accessioned | 2026-07-07T10:10:24Z | |
| dc.date.available | 2026-07-07T10:10:24Z | |
| dc.description | {\it A unit cube in $k$-dimension (or a $k$-cube) is defined as the cartesian product $R_1 \times R_2 \times ... \times R_k$, where each $R_i$ is a closed interval on the real line of the form $[a_i, a_i+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) \leq \lfloor\frac{2n}{3}\rfloor$. Recently it has been shown that for a graph $G$, $cub(G) \leq 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 \cup B, E)$ with $|A| = n_1$, $|B| = n_2$, $n_1 \leq n_2$, and $Δ' = \min\{Δ_A, Δ_B\}$, where $Δ_A = {max}_{a \in A}d(a)$ and $Δ_B = {max}_{b \in B}d(b)$, $d(a)$ and $d(b)$ being the degree of $a$ and $b$ in $G$ respectively, $cub(G) \leq 2(Δ'+2) \lceil \ln n_2 \rceil$. We also give an efficient randomized algorithm to construct the cube representation of $G$ in $3(Δ'+2)\lceil \ln n_2 \rceil$ dimensions. The reader may note that in general $Δ'$ can be much smaller than $Δ$.} | |
| dc.description | 7 pages | |
| dc.identifier | https://arxiv.org/abs/0810.2697 | |
| dc.identifier | http://arxiv.org/abs/0810.2697 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/171592 | |
| dc.subject | Discrete Mathematics | |
| dc.title | On the cubicity of bipartite graphs | |
| dc.type | text |