Namespaces
Variants
Actions

Difference between revisions of "Graph, extremal"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044920/g0449201.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044920/g0449202.png" /> one seeks the largest possible number of edges of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044920/g0449203.png" />-vertex graph without complete subgraphs with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044920/g0449204.png" /> vertices. It was found that this number is
+
{{TEX|done}}
 +
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044920/g0449205.png" /></td> </tr></table>
+
$$\frac{k-1}{2k}(n^2-r^2)+\frac{r(r-1)}{2},$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044920/g0449206.png" />. A complete <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044920/g0449207.png" />-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 [[#References|[3]]].
+
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 [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044920/g0449208.png" /> and a selection of one-place operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044920/g0449209.png" /> on the graphs be given. A graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044920/g04492010.png" /> having the property <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044920/g04492011.png" /> is said to be critical with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044920/g04492012.png" /> and the operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044920/g04492013.png" /> if, after the execution of any one of the above operations, the resulting graph no longer has property <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044920/g04492014.png" />. It is assumed that the set of graphs which do not display property <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044920/g04492015.png" /> is closed with respect to these operations. Property <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044920/g04492016.png" /> may be, for example, being connected, planar or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044920/g04492017.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044920/g04492018.png" /> and the complete bipartite graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044920/g04492019.png" /> (cf. [[Graph, planar|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.
+
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|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.
  
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/g044920a.gif" />
 
<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/g044920a.gif" />
Line 11: Line 12:
 
Figure: g044920a
 
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 (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044920/g04492020.png" />-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.
+
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====
 
====References====

Revision as of 16:20, 28 August 2014

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)
How to Cite This Entry:
Graph, extremal. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Graph,_extremal&oldid=12976
This article was adapted from an original article by A.A. Sapozhenko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article