Two extremal problems in graph theory
The electronic journal of combinatorics, Tome 1 (1994)
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$.
@article{10_37236_1182,
author = {Richard A. Brualdi and Stephen Mellendorf},
title = {Two extremal problems in graph theory},
journal = {The electronic journal of combinatorics},
year = {1994},
volume = {1},
doi = {10.37236/1182},
zbl = {0810.05041},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1182/}
}
Richard A. Brualdi; Stephen Mellendorf. Two extremal problems in graph theory. The electronic journal of combinatorics, Tome 1 (1994). doi: 10.37236/1182
Cité par Sources :