On the decomposition of graphs into complete bipartite subgraphs

Abstract

For a given graph G, we consider a B-decomposition of G, i. e., a decomposition of G into complete bipartite subgraphs G ₁..., G _t , such that any edge of G is in exactly one of the G′ _i s. Let α(G; B) denote the minimum value of $\sum\limits_i {|V(G_i )|}$ over all B-decompositions of G. Let α(n; B) denote the maximum value of α(G; B) over all graphs on n vertices.

A B-covering of G is a collection of complete bipartite subgraphs G′₁,G′₂,..., G′ _t , such that any edge of G is in at least one of the G′ _i . Let β(G; B) denote the minimum value of $\sum\limits_i {|V(G'_i )|}$ over all B-coverings of G and let β(n; B) denote the maximum value of β(G; B) over all graphs on n vertices.

In this paper, we show that for any positive ε, we have

$$(1 - \varepsilon )\frac{{n^2 }} {{2e\log n}} < \beta (n;B) \leqq \alpha (n;B) < (1 + \varepsilon )\frac{{n^2 }} {{2\log n}}$$

where e = 2.718... is the base of natural logarithms, provided n is sufficiently large.

Work done while a consultant at Bell Laboratories.