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 Gi such that any edge of G is in at least (respectively exactly) one Gi (i = 1,2,...,t). Let \beta(G; B) (respectively \alpha(G; B)) denote the minimum value of sumti = 1|V(Gi)| 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{n2}{2e log n} < \beta(n; B) \leq \alpha(n; B) < (1+\epsilon)\frac{n2}{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 Gn denote the set of the 2\binom{n{2}} labelled graphs on n vertices, it is conjectured that

limn ––> oosumG in Gn\alpha(n; B)/2\binom{n{2}}n2/ log n

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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page