##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 531.05042

**Autor: ** Chung, F.R.K.; Erdös, Paul; Spencer, Joel

**Title: ** On the decomposition of graphs into complete bipartite subgraphs. (In English)

**Source: ** Studies in pure mathematics, Mem. of P. Turán, 95-101 (1983).

**Review: ** [For the entire collection see Zbl 512.00007.]

A B-covering (respectively B-decomposition) of a graph G is a collection of complete bipartite graphs G_{i} such that any edge of G is in at least (respectively exactly) one G_{i} (i = 1,2,...,t). Let \beta(G; B) (respectively \alpha(G; B)) denote the minimum value of **sum**^{t}_{i = 1}|V(G_{i})| over all B-coverings (respectively B-decompositions) of G. Let \beta(n; B) (respectively \alpha(n; B)) denote the maximum value of \beta(G; B) (respectively \alpha(G; B)) as G ranges over all graphs on n vertices. "In this paper we show that, for any positive \epsilon, we have (1- \epsilon)\frac{n^{2}}{2e log n} < \beta(n; B) \leq \alpha(n; B) < (1+\epsilon)\frac{n^{2}}{2 log n}, where e is the base of the natural logarithms, provided n is sufficiently large." A number of related questions and conjectures are discussed. For example, if G_{n} denote the set of the 2^{\binom{n}{2}} labelled graphs on n vertices, it is conjectured that

**lim**_{n ––> oo}**sum**_{G in Gn}\alpha(n; B)/2^{\binom{n}{2}}n^{2}/ log n exists.

**Reviewer: ** W.G.Brown

**Classif.: ** * 05C35 Extremal problems (graph theory)

05C99 Graph theory

60C05 Combinatorial probability

**Keywords: ** decomposition; covering; bipartite graph

**Citations: ** Zbl 512.00007

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag