On some variations of extremal graph problems

Gabriel Semanišin

Discussiones Mathematicae Graph Theory (1997)

  • Volume: 17, Issue: 1, page 67-76
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Gabriel Semanišin. "On some variations of extremal graph problems." Discussiones Mathematicae Graph Theory 17.1 (1997): 67-76. <http://eudml.org/doc/270170>.

@article{GabrielSemanišin1997,
abstract = { 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. },
author = {Gabriel Semanišin},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hereditary properties of graphs; maximal graphs; extremal graphs; saturated graphs; hereditary graph properties},
language = {eng},
number = {1},
pages = {67-76},
title = {On some variations of extremal graph problems},
url = {http://eudml.org/doc/270170},
volume = {17},
year = {1997},
}

TY - JOUR
AU - Gabriel Semanišin
TI - On some variations of extremal graph problems
JO - Discussiones Mathematicae Graph Theory
PY - 1997
VL - 17
IS - 1
SP - 67
EP - 76
AB - 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.
LA - eng
KW - hereditary properties of graphs; maximal graphs; extremal graphs; saturated graphs; hereditary graph properties
UR - http://eudml.org/doc/270170
ER -

References

top
  1. [1] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed., Advances in Graph Theory (Vishwa Intern. Publication, Gulbarga, 1991) 41-68. 
  2. [2] P. Erdős, Some recent results on extremal problems in graph theory, Results in: P. Rosentstiehl, ed., Theory of Graphs (Gordon and Breach New York; Dunod Paris, 1967) 117-123; MR37#2634. 
  3. [3] P. Erdős, On some new inequalities concerning extremal properties of graphs, in: P. Erdős and G. Katona, eds., Theory of Graphs (Academic Press, New York, 1968) 77-81; MR38#1026. 
  4. [4] J. Kratochvíl, P. Mihók and G. Semanišin, Graphs maximal with respect to hom-properties, Discussiones Mathematicae Graph Theory 17 (1997) 77-88, doi: 10.7151/dmgt.1040. Zbl0905.05038
  5. [5] R. Lick and A. T. White, k-degenerate graphs, Canadian J. Math. 22 (1970) 1082-1096; MR42#1715. Zbl0202.23502
  6. [6] P. Mihók, On graphs critical with respect to vertex partition numbers, Discrete Math. 37 (1981) 123-126, doi: 10.1016/0012-365X(81)90146-1. Zbl0471.05038
  7. [7] P. Mihók and G. Semanišin, On the chromatic number of reducible hereditary properties (submitted). Zbl1055.05061
  8. [8] P. Mihók and G. Semanišin, Reducible properties of graphs, Discussiones Math. Graph Theory 15 (1995) 11-18; MR96c:05149, doi: 10.7151/dmgt.1002. Zbl0829.05057
  9. [9] M. Simonovits, A method for solving extremal problems in graph theory, stability problems, in: P. Erdős and G. Katona, eds., Theory of Graphs (Academic Press, New York, 1968) 279-319; MR 38#2056. 
  10. [10] M. Simonovits, Extremal graph problems with symmetrical extremal graphs. Additional chromatical conditions, Discrete Math. 7 (1974) 349-376; MR49#2459. Zbl0274.05113
  11. [11] M. Simonovits, Extremal graph theory, in: L.W. Beineke and R.J. Wilson, eds., Selected Topics in Graph Theory vol. 2 (Academic Press, London, 1983) 161-200. 
  12. [12] P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941) 436-452 (Hungarian); MR8,284j. 
  13. [13] P. Turán, On the theory of graph, Colloquium Math. 3 (1954) 19-30; MR15,476b. 
  14. [14] L. Kászonyi and Z. Tuza, Saturated graphs with minimal number of edges, J. Graph Theory 10 (1986) 203-210, doi: 10.1002/jgt.3190100209. Zbl0593.05041

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.