##
**Zentralblatt MATH**

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

**Zbl.No: ** 364.05033

**Autor: ** Busolini, D.T.; Erdös, Paul

**Title: ** On a problem in extremal graph theory. (In English)

**Source: ** J. Comb. Theory, Ser. B 23, 251-254 (1977).

**Review: ** From the authors introduction. Let G(n,m) denote a graph (V,E) with n vertices and m edges and K_{1} a complete graph with i vertices. *P.Turán* proved that every G(n,T(n,k)) contains a K_{k}, where T(n,k) = \frac{k-2}{2(k-1)}(n^{2}-r^{2})+\binom r2+1, r\equiv n(mod k-1) and 0 \leq r \leq k-2.

The problem: For k a positive integer a graph g(n,m) is said to posses property P(k) if n \geq \binom{k+1}{2} and it contains vertex-disjoint subgraphs K_{1},K_{2},...,K_{k}. Find the least positive integer T^*(n,k) such that every G(n,T^*(n,k)) has P(k). Clearly T^*(n,k) \geq T(n,k). The following results are proved.

Theorem 1. If n \geq 9k^{2}/k then T^*(n,k) = T(n,k).

Theorem 2. There exists \epsilon > 0 and k_{0} = k_{0}(\epsilon) such that if k > k_{0} and \binom{k+1}{2} \leq n \leq \binom{k+1}{2}+\epsilon k^{2} then T^*(n,k) > T(n,k). Put n = \binom{k+1}{2}+t and let e(t,k) denote the number of edges of the n-vertex graph X(t,k) whose complement consists of a K_{k+t+1} together with n-k-t-1 isolated vertices.

Theorem 3. There exists k_{0} = k_{0}(t) such that if k > k_{0} then T^*(n,k) = e(t,k)+1 and the only G(n,e(t,k)) without P(k) is X(t,k).

**Reviewer: ** J.E.Graver

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

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag