Maximal graphs with respect to hereditary properties

Izak Broere; Marietjie Frick; Gabriel Semanišin

Discussiones Mathematicae Graph Theory (1997)

  • Volume: 17, Issue: 1, page 51-66
  • ISSN: 2083-5892

Abstract

top
A property of graphs is a non-empty set of graphs. A property P is called hereditary if every subgraph of any graph with property P also has property P. Let P₁, ...,Pₙ be properties of graphs. We say that a graph G has property P₁∘...∘Pₙ if the vertex set of G can be partitioned into n sets V₁, ...,Vₙ such that the subgraph of G induced by Vi has property P i ; i = 1,..., n. A hereditary property R is said to be reducible if there exist two hereditary properties P₁ and P₂ such that R = P₁∘P₂. If P is a hereditary property, then a graph G is called P- maximal if G has property P but G+e does not have property P for every e ∈ E([G̅]). We present some general results on maximal graphs and also investigate P-maximal graphs for various specific choices of P, including reducible hereditary properties.

How to cite

top

Izak Broere, Marietjie Frick, and Gabriel Semanišin. "Maximal graphs with respect to hereditary properties." Discussiones Mathematicae Graph Theory 17.1 (1997): 51-66. <http://eudml.org/doc/270401>.

@article{IzakBroere1997,
abstract = {A property of graphs is a non-empty set of graphs. A property P is called hereditary if every subgraph of any graph with property P also has property P. Let P₁, ...,Pₙ be properties of graphs. We say that a graph G has property P₁∘...∘Pₙ if the vertex set of G can be partitioned into n sets V₁, ...,Vₙ such that the subgraph of G induced by Vi has property $P_i$; i = 1,..., n. A hereditary property R is said to be reducible if there exist two hereditary properties P₁ and P₂ such that R = P₁∘P₂. If P is a hereditary property, then a graph G is called P- maximal if G has property P but G+e does not have property P for every e ∈ E([G̅]). We present some general results on maximal graphs and also investigate P-maximal graphs for various specific choices of P, including reducible hereditary properties.},
author = {Izak Broere, Marietjie Frick, Gabriel Semanišin},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hereditary property of graphs; maximal graphs; vertex partition; hereditary property; reducible property; -degenerate graph},
language = {eng},
number = {1},
pages = {51-66},
title = {Maximal graphs with respect to hereditary properties},
url = {http://eudml.org/doc/270401},
volume = {17},
year = {1997},
}

TY - JOUR
AU - Izak Broere
AU - Marietjie Frick
AU - Gabriel Semanišin
TI - Maximal graphs with respect to hereditary properties
JO - Discussiones Mathematicae Graph Theory
PY - 1997
VL - 17
IS - 1
SP - 51
EP - 66
AB - A property of graphs is a non-empty set of graphs. A property P is called hereditary if every subgraph of any graph with property P also has property P. Let P₁, ...,Pₙ be properties of graphs. We say that a graph G has property P₁∘...∘Pₙ if the vertex set of G can be partitioned into n sets V₁, ...,Vₙ such that the subgraph of G induced by Vi has property $P_i$; i = 1,..., n. A hereditary property R is said to be reducible if there exist two hereditary properties P₁ and P₂ such that R = P₁∘P₂. If P is a hereditary property, then a graph G is called P- maximal if G has property P but G+e does not have property P for every e ∈ E([G̅]). We present some general results on maximal graphs and also investigate P-maximal graphs for various specific choices of P, including reducible hereditary properties.
LA - eng
KW - hereditary property of graphs; maximal graphs; vertex partition; hereditary property; reducible property; -degenerate graph
UR - http://eudml.org/doc/270401
ER -

References

top
  1. [1] G. Benadé, I. Broere, B. Jonck and M. Frick, Uniquely ( m , k ) τ -colourable graphs and k-τ-saturated graphs, Discrete Math. 162 (1996) 13-22, doi: 10.1016/0012-365X(95)00301-C. Zbl0870.05026
  2. [2] M. Borowiecki, I. Broere and P. Mihók, Minimal reducible bounds for planar graphs, submitted. Zbl0945.05022
  3. [3] M. Borowiecki, J. Ivančo, P. Mihók and G. Semanišin, Sequences realizable by maximal k-degenerate graphs, J. Graph Theory 19 (1995) 117-124; MR96e:05078. Zbl0813.05061
  4. [4] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed., Advances in Graph Theory (Vishwa International Publication, Gulbarga, 1991) 41-68. 
  5. [5] I. Broere, M. Frick and P. Mihók, On the order of uniquely partitionable graphs, submitted. Zbl0906.05058
  6. [6] G. Chartrand and L. Lesniak, Graphs and Digraphs, (Wadsworth & Brooks/Cole, Monterey California, 1986). Zbl0666.05001
  7. [7] P. Erdős and T. Gallai, On the minimal number of vertices representing the edges of a graph, Magyar Tud. Akad. Math. Kutató Int. Közl. 6 (1961) 181-203; MR 26#1878. Zbl0101.41001
  8. [8] Z. Filáková, P. Mihók and G. Semanišin, On maximal k-degenerate graphs, to appear in Math. Slovaca. 
  9. [9] A. Hajnal, A theorem on k-saturated graphs, Canad. J. Math. 17 (1965) 720-724; MR31#3354. Zbl0129.39901
  10. [10] L. Kászonyi and Zs. Tuza, Saturated graphs with minimal number of edges, J. Graph Theory 10 (1986) 203-210, doi: 10.1002/jgt.3190100209. Zbl0593.05041
  11. [11] 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
  12. [12] R. Lick and A.T. White, k-degenerate graphs, Canad. J. Math. 22 (1970) 1082-1096; MR42#1715. Zbl0202.23502
  13. [13] P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: M. Borowiecki and Z. Skupień, eds., Graphs, Hypergraphs and Matroids (Zielona Góra, 1985) 49-58. Zbl0623.05043
  14. [14] 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
  15. [15] J. Mitchem, An extension of Brooks' theorem to r-degenerate graphs, Discrete Math. 17 (1977) 291-298; MR 55#12561. Zbl0351.05124
  16. [16] J. Mitchem, Maximal k-degenerate graphs, Utilitas Math. 11 (1977) 101-106. Zbl0348.05109
  17. [17] G. Semanišin, On some variations of extremal graph problems, Discussiones Mathematicae Graph Theory 17 (1997) 67-76, doi: 10.7151/dmgt.1039. Zbl0904.05046
  18. [18] J.M.S. Simoes-Pereira, On graphs uniquely partitionable into n-degenerate subgraphs, in: Infinite and finite sets - Colloquia Math. Soc. J. Bólyai 10 (North-Holland Amsterdam, 1975) 1351-1364; MR53#2758. 
  19. [19] J.M.S. Simoes-Pereira, A survey on k-degenerate graphs, Graph Theory Newsletter 5 (6) (75/76) 1-7; MR 55#199. Zbl0331.05135

Citations in EuDML Documents

top
  1. Jan Kratochvíl, Peter Mihók, Gabriel Semanišin, Graphs maximal with respect to hom-properties
  2. Bohdan Zelinka, Graphs maximal with respect to absence of hamiltonian paths
  3. Izak Broere, Marietjie Frick, Peter Mihók, The order of uniquely partitionable graphs
  4. Ewa Drgas-Burchardt, A note on joins of additive hereditary graph properties
  5. Alastair Farrugia, R. Bruce Richter, Unique factorisation of additive induced-hereditary properties
  6. Izak Broere, Michael Dorfling, Jean E. Dunbar, Marietjie Frick, A path(ological) partition problem
  7. Marietjie Frick, A Survey of the Path Partition Conjecture
  8. Mieczysław Borowiecki, Izak Broere, Marietjie Frick, Peter Mihók, Gabriel Semanišin, A survey of hereditary properties of graphs

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.