Extremal graph theory

The extremal graph theory is a branch of mathematics . It examines which graphs of a given class (such as the class of graphs without a Hamiltonian circle ) maximize or minimize a certain graph parameter (such as the maximum number of edges or the edge density ).

One result of extremal graph theory is, for example, that graphs with nodes that do not contain a circle of length 3 have at most edges. This is a special case of Pál Turán's theorem (1941), who founded the extremal graph theory: ${\displaystyle n}$ ${\displaystyle n^{2}/4}$

Turán's theorem : A graph with n nodes without p- clique (complete subgraph with p nodes),, has at most edges. ${\displaystyle p\geq 2}$ ${\displaystyle \left(1-{\frac {1}{p-1}}\right){\frac {n^{2}}{2}}}$

If one defines the number of a graph as the maximum number of edges that a graph with nodes and without a subgraph that is too isomorphic can have, this statement can be made ${\displaystyle H}$ ${\displaystyle \mathrm {ex} (n,H)}$ ${\displaystyle n}$ ${\displaystyle H}$

${\displaystyle \mathrm {ex} (n,K_{p})\leq \left(1-{\frac {1}{p-1}}\right){\frac {n^{2}}{2}}}$

rephrase, where the full graph is with nodes. If one denotes the circle graph with nodes, then one obtains as a further example ${\displaystyle K_{p}}$ ${\displaystyle p}$ ${\displaystyle C_{p}}$ ${\displaystyle p}$

${\displaystyle K_{5}}$ extended by a node and an edge

${\displaystyle \mathrm {ex} (p,C_{p})\,=\,1+{\frac {(p-1)(p-2)}{2}}}$.

The graph, which is created by adding a further node and an edge, has no subgraphs and edges that are too isomorphic (see adjacent drawing for ). The addition of a further edge obviously leads to a subgraph that is too isomorphic. ${\displaystyle K_{p-1}}$ ${\displaystyle C_{p}}$ ${\displaystyle 1+{\frac {(p-1)(p-2)}{2}}}$ ${\displaystyle p=6}$ ${\displaystyle C_{p}}$

See also

• Ramsey theory

literature

• Béla Bollobás : Extremal graph theory. Academic Press, London 1978, ISBN 0-12-111750-2 .
• Frank Harary : Graph Theory. R. Oldenbourg, Munich 1974, ISBN 3-486-34191-X .

Individual evidence

1. ↑ Turán: On an extremal problem in graph theory. In: Math.Fiz.Lapok. Vol. 48, 1941, p. 436.
2. ^ Aigner, Günter M. Ziegler : Proofs from the Book. Jumper. In chapter 32 five pieces of evidence are given, among others by Turán and Paul Erdős .