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 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