Added to Favorites

Related Searches

Nearby Words

Extremal graph theory is a branch of mathematics. _{3}; for instance, the Zarankiewicz problem concerns the largest graph that does not contain a fixed complete bipartite graph as a subgraph. Turán also found the (unique) largest graph not containing K_{k} which is named after him, namely Turán graph. This graph has
_{4}, the largest graph on n vertices not containing C_{4} has
## See also

## References

In the narrow sense, extremal graph theory studies the graphs which are extremal among graphs with a certain property. There are various meanings for the word extremal: with the largest number of edges, the largest minimum degree, the smallest diameter, etc. In a broader sense, various other related questions can be included into extremal graph theory. In that case, the term extremal graph theory can encompass a large part of graph theory.

A typical result in extremal graph theory is Turán's theorem. It answers the following question. What is the maximum possible number of edges in an undirected graph G with n vertices which does not contain K_{3} (three vertices A, B, C with edges AB, AC, BC; i.e. a triangle) as a subgraph? The bipartite graph where the partite sets differ in their size by at most 1, is the only extremal graph with this property. It contains

- $leftlfloor\; frac\{n^2\}\{4\}\; rightrfloor$

- $leftlfloor\; frac\{(k-2)\; n^2\}\{2(k-1)\}\; rightrfloor\; =\; leftlfloor\; left(1-\; frac\{1\}\{k-1\}\; right)\; frac\{n^2\}\{2\}\; rightrfloor$

- $left(frac\{1\}\{2\}+o(1)right)\; n^\{3/2\}$

- Béla Bollobás. Extremal Graph Theory. New York: Academic Press, 1978.
- Béla Bollobás. Modern Graph Theory, chapter 4: Extremal Problems. New York: Springer, 1998.
- M. Simonovits, Slides from the Chorin summer school lectures, 2006.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Tuesday September 02, 2008 at 13:47:55 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Tuesday September 02, 2008 at 13:47:55 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.