The Turán graph T(n,r) is an example of an extremal graph. It has the maximum possible number of edges for a graph on n vertices without (r + 1)-cliques. This is T(13,4).
Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local substructure.
[1]
Results in extremal graph theory deal with quantitative connections between various graph properties, both global (such as the number of vertices and edges) and local (such as the existence of specific subgraphs), and problems in extremal graph theory can often be formulated as optimization problems: how big or small a parameter of a graph can be, given some constraints that the graph has to satisfy?
[2]
A graph that is an optimal solution to such an optimization problem is called an extremal graph, and extremal graphs are important objects of study in extremal graph theory.
Extremal graph theory is closely related to fields such as Ramsey theory, spectral graph theory, computational complexity theory, and additive combinatorics, and frequently employs the probabilistic method.
^
Diestel, Reinhard (2010), Graph Theory (4th ed.), Berlin, New York: Springer-Verlag, pp. 169–198, ISBN 978-3-642-14278-9, archived from the original on 2017-05-28, retrieved 2013-11-18
^
Alon, Noga; Krivelevich, Michael (2008). "Extremal and Probabilistic Combinatorics". In Gowers, Timothy; Barrow-Green, June; Leader, Imre (eds.). The Princeton Companion to Mathematics. Princeton, New Jersey: Princeton University Press. pp. 562–575. doi:10.1515/9781400830398. ISBN 978-0-691-11880-2. JSTOR j.ctt7sd01. LCCN 2008020450. MR 2467561. OCLC 227205932. OL 19327100M. Zbl 1242.00016.
and 17 Related for: Extremal graph theory information
Extremalgraphtheory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory...
areas of spectral graphtheory, extremalgraphtheory and random graphs, in particular in generalizing the Erdős–Rényi model for graphs with general degree...
graphtheory Geometric graphtheoryExtremalgraphtheory Probabilistic graphtheory Topological graphtheory Combinatorics Group theory Knot theory Ramsey...
Dempster-Shafer theory Dimension theory Distribution theory Dynamical systems theory Elimination theory Ergodic theoryExtremalgraphtheory Field theory Formal...
spectral graphtheory, a Ramanujan graph is a regular graph whose spectral gap is almost as large as possible (see extremalgraphtheory). Such graphs are...
In the mathematical discipline of graphtheory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges...
the mathematical field of graphtheory, the friendship graph (or Dutch windmill graph or n-fan) Fn is a planar, undirected graph with 2n + 1 vertices and...
Extremal combinatorics is a field of combinatorics, which is itself a part of mathematics. Extremal combinatorics studies how large or how small a collection...
In graphtheory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges...
many edges. Thus it has its application in extremalgraphtheory, additive combinatorics and Ramsey theory. Let u , n , r , m , t ∈ N {\displaystyle u...
In graphtheory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding...
Hungarian-style combinatorics, particularly Ramsey theory, extremalgraphtheory, combinatorial number theory, and probabilistic methods in combinatorics. Fox...
In the mathematical field of graphtheory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first...
Global Information