|
|
|
|
|
Extremal Graph TheoryExtremal 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 Turn'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 Turn graph, it contains -
edges. Similar questions has been studied with various other subgraphs H instead of K3. Turn also found the largest graph not containing Kk. This graph has -
edges. For C4, the largest graph on n vertices not containing C4 has -
edges. References - Bela Bollobas. Extremal Graph Theory. New York: Academic Press, 1978.
- Bela Bollobas. Modern Graph Theory. (Chapter 4: Extremal Problems.) New York: Springer, 1998.
- Eric W. Weisstein. Extremal Graph Theory. From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/ExtremalGraphTheory.html
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|