- Tytuł:
- On some variations of extremal graph problems
- Autorzy:
- Semanišin, Gabriel
- Powiązania:
- https://bibliotekanauki.pl/articles/972027.pdf
- Data publikacji:
- 1997
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
hereditary properties of graphs
maximal graphs
extremal graphs
saturated graphs - Opis:
-
A set P of graphs is termed hereditary property if and only if it contains all subgraphs of any graph G belonging to P. A graph is said to be maximal with respect to a hereditary property P (shortly P-maximal) whenever it belongs to P and none of its proper supergraphs of the same order has the property P. A graph is P-extremal if it has a the maximum number of edges among all P-maximal graphs of given order. The number of its edges is denoted by ex(n, P). If the number of edges of a P-maximal graph is minimum, then the graph is called P-saturated and its number of edges is denoted by sat(n, P).
In this paper, we consider two famous problems of extremal graph theory. We shall translate them into the language of P-maximal graphs and utilize the properties of the lattice of all hereditary properties in order to establish some general bounds and particular results. Particularly, we shall investigate the behaviour of sat(n,P) and ex(n,P) in some interesting intervals of the mentioned lattice. - Źródło:
-
Discussiones Mathematicae Graph Theory; 1997, 17, 1; 67-76
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł