Graph, extremal

A graph on which a certain numerical characteristic assumes its maximum or its minimum value. The usual practice is to find the extremal values of a certain characteristic by imposing restrictions on other numerical characteristics and properties. The problem often consists in describing the set of appropriate extremal graphs. E.g., for given positive numbers $n$ and $k$ one seeks the largest possible number of edges of an $n$-vertex graph without complete subgraphs with $k+1$ vertices. It was found that this number is

$$\frac{k-1}{2k}(n^2-r^2)+\frac{r(r-1)}{2},$$

where $n=k[n/k]+r$. A complete $k$-partite graph, the cardinalities of the parts of which differ by not more than one, is unique, up to an isomorphism of the extremal graph [3].

The numerical characteristics under study attain their global extrema on extremal graphs. The so-called critical graphs can be considered as locally optimal. Let some property $A$ and a selection of one-place operations $O_1,\dots,O_n$ on the graphs be given. A graph $G$ having the property $A$ is said to be critical with respect to $A$ and the operations $O_1,\dots,O_n$ if, after the execution of any one of the above operations, the resulting graph no longer has property $A$. It is assumed that the set of graphs which do not display property $A$ is closed with respect to these operations. Property $A$ may be, for example, being connected, planar or $k$-chromatic, while the operations include the removal or the addition of a vertex or an edge, contraction of an edge, etc. Thus, Petersen's graph (see Fig.) is critical with respect to having edge chromatic number 4 with respect to the operation of edge removal. The complete five-vertex graph $K_5$ and the complete bipartite graph $K_{3,3}$ (cf. Graph, planar, Figure 1), each part of which has three vertices, are critical with respect to the property of not being planar with respect to the operations of edge removal, edge contraction and vertex removal.

Figure: g044920a

In the study of the properties and characteristics of graphs it is useful to study their critical subgraphs, i.e. subgraphs with certain properties which are minimal (or maximal) with respect to inclusion. Examples of such subgraphs include connected ($k$-connected) components and spanning trees. Extremal and critical graphs serve to describe classes of graphs with given properties and numerical characteristics; to establish a connection between the various properties and the numerical characteristics; and to establish whether or not a graph possesses a given property.

References

[1]	F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9
[2]	A.A. Zykov, "The theory of finite graphs" , 1 , Novosibirsk (1969) (In Russian)
[3]	P. Turán, "An extremal problem in graph theory" Mat. Fiz. Lapok , 48 (1941) pp. 436–452 ((in Hungarian; German summary))

Comments

P. Turán and P. Erdös laid the foundations of extremal graph theory. A comprehensive account of this point of view of graph theory can be found in [a1].

References

[a1]	B. Bollobas, "Extremal graph theory" , Acad. Press (1978)