Two Extremal Problems in Graph Theory

Abstract

We consider the following two problems. (1) Let $t$ and $n$ be positive integers with $n\geq t\geq 2$. Determine the maximum number of edges of a graph of order $n$ that contains neither $K_t$ nor $K_{t,t}$ as a subgraph. (2) Let $r$, $t$ and $n$ be positive integers with $n\geq rt$ and $t\geq 2$.

Determine the maximum number of edges of a graph of order $n$ that does not contain $r$ disjoint copies of $K_t$. Problem 1 for $n < 2t$ is solved by Turán's theorem and we solve it for $n=2t$. We also solve Problem 2 for $n=rt$.