Two Extremal Problems in Graph Theory

Richard A. Brualdi, Stephen Mellendorf

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


Full Text: PDF