On the cubicity of bipartite graphs

-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

,

c u b (G) l e q l f l o o r f r a c 2 n 3 f l o o r

. Recently it has been shown that for a graph

G

,

c u b (G) l e q 4 (D e l t a + 1) l n n

, where

n

and

D e l t a

are the number of vertices and maximum degree of

G

, respectively. In this paper, we show that for a bipartite graph

G = (A c u p B, E)

with

| A | = n_{1}

,

| B | = n_{2}

,

n_{1} l e q n_{2}

, and

D e l t a^{'} = m i n D e l t a_{A}, D e l t a_{B}

, where

D e l t a_{A} = {m a x}_{a i n A} d (a)

and

D e l t a_{B} = {m a x}_{b i n B} d (b)

,

d (a)

and

d (b)

being the degree of

a

and

b

in

G

respectively,

c u b (G) l e q 2 (D e l t a^{'} + 2) l c e i l l n n_{2} c e i l

. We also give an efficient randomized algorithm to construct the cube representation of

G

in

3 (D e l t a^{'} + 2) l c e i l l n n_{2} c e i l

dimensions. The reader may note that in general

D e l t a^{'}

can be much smaller than

D e l t a

.}

Recommendations

Cites work

Cited in

(8)

This page was built for publication: On the cubicity of bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q987780)