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 K1 a complete graph with i vertices. P.Turán proved that every G(n,T(n,k)) contains a Kk, where T(n,k) = \frac{k-2}{2(k-1)}(n2-r2)+\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 K1,K2,...,Kk. 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 9k2/k then T^*(n,k) = T(n,k).
Theorem 2. There exists \epsilon > 0 and k0 = k0(\epsilon) such that if k > k0 and \binom{k+1}{2} \leq n \leq \binom{k+1}{2}+\epsilon k2 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 Kk+t+1 together with n-k-t-1 isolated vertices.
Theorem 3. There exists k0 = k0(t) such that if k > k0 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