Definitions

# Extremal graph theory

Extremal graph theory is a branch of mathematics.

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 K3 (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\left\{n^2\right\}\left\{4\right\} rightrfloor$
edges. Similar questions have been studied with various other subgraphs H instead of K3; 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 Kk which is named after him, namely Turán graph. This graph has
$leftlfloor frac\left\{\left(k-2\right) n^2\right\}\left\{2\left(k-1\right)\right\} rightrfloor = leftlfloor left\left(1- frac\left\{1\right\}\left\{k-1\right\} right\right) frac\left\{n^2\right\}\left\{2\right\} rightrfloor$
edges. For C4, the largest graph on n vertices not containing C4 has
$left\left(frac\left\{1\right\}\left\{2\right\}+o\left(1\right)right\right) n^\left\{3/2\right\}$
edges.

## References

1. Béla Bollobás. Extremal Graph Theory. New York: Academic Press, 1978.
2. Béla Bollobás. Modern Graph Theory, chapter 4: Extremal Problems. New York: Springer, 1998.
3. M. Simonovits, Slides from the Chorin summer school lectures, 2006.
Search another word or see Extremal graph theoryon Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
• Please Login or Sign Up to use the Recent Searches feature