ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2019: 0.600
Rejection Rate (2018-2019): c. 84%
Discussiones Mathematicae Graph Theory 17(1) (1997)
Department of Geometry and Algebra
Faculty of Science, P.J. Šafárik University
Jesenná 5, 041 54 Košice, Slovak Republic
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.
Keywords: hereditary properties of graphs, maximal graphs, extremal graphs,
1991 Mathematics Subject Classification: 05C15, 05C35.