Extremal graph theory

From Wikipedia, the free encyclopedia

You have new messages (last change).

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) as a subgraph? This graph is known as a Turán graph and contains

\left\lfloor \frac{n^2}{4} \right\rfloor

edges. Similar questions has been studied with various other subgraphs H instead of K3. Turán also found the largest graph not containing Kk. This graph has

\left\lfloor \frac{(k-2) n^2}{2(k-1)} \right\rfloor

edges. For C4, the largest graph on n vertices not containing C4 has

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

edges.

[edit] See also

[edit] 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. Eric W. Weisstein. "Extremal Graph Theory." From MathWorld – A Wolfram Web Resource. [1]
  4. M. Simonovits, Slides from the Chorin summer school lectures, 2006. [2]
Retrieved from "http://en.wikipedia.org../../../e/x/t/Extremal_graph_theory.html"