FACTOID # 6: Michigan is ranked 22nd in land area, but since 41.27% of the state is composed of water, it jumps to 11th place in total area.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


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

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

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

edges.


References

  1. Bela Bollobas. Extremal Graph Theory. New York: Academic Press, 1978.
  2. Bela Bollobas. 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] (http://mathworld.wolfram.com/ExtremalGraphTheory.html)

  Results from FactBites:
 
Graph theory - Wikipedia, the free encyclopedia (1209 words)
Informally, a graph is a set of objects called vertices (or nodes) connected by links called edges (or arcs) which can be directed (assigned a direction).
Another way to extend basic graphs is by making the edges to the graph directional (A links to B, but B does not necessarily link to A, as in webpages), technically called a directed graph or digraph.
Graphs are represented graphically by drawing a dot for every vertex, and drawing an arc between two vertices if they are connected by an edge.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m