DMGT

Discussiones Mathematicae Graph Theory 17(1) (1997) 51-66
DOI: https://doi.org/10.7151/dmgt.1038

MAXIMAL GRAPHS WITH RESPECT TO HEREDITARY PROPERTIES

Izak Broere

Department of Mathematics
Rand Afrikaans University
P.O. Box 524, Auckland Park, 2006 South Africa

Marietjie Frick

Department of Mathematics, Applied Mathematics and Astronomy
University of South Africa
P.O. Box 392, Pretoria, 0001 South Africa

Gabriel Semanišin

Department of Geometry and Algebra
P.J.Šafárik University
041 54 Košice, Slovak Republic

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_n be properties of graphs. We say that a graph G has property P₁ º…ºP_n if the vertex set of G can be partitioned into n sets V₁, …,V_n such that the subgraph of G induced by V_i 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.

Keywords: hereditary property of graphs, maximal graphs, vertex partition.

1991 Mathematics Subject Classification: 05C15, O5C75.

References

[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.
[2]	M. Borowiecki, I. Broere and P. Mihók, Minimal reducible bounds for planar graphs, submitted.
[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.
[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]	I. Broere, M. Frick and P. Mihók, On the order of uniquely partitionable graphs, submitted.
[6]	G. Chartrand and L. Lesniak, Graphs and Digraphs, (Wadsworth & Brooks/Cole, Monterey California, 1986).
[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.
[8]	Z. Filáková, P. Mihók and G. Semanišin, On maximal k-degenerate graphs, to appear in Math. Slovaca.
[9]	A. Hajnal, A theorem on k-saturated graphs, Canad. J. Math. 17 (1965) 720-724; MR31#3354.
[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.
[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.
[12]	R. Lick and A.T. White, k-degenerate graphs, Canad. J. Math. 22 (1970) 1082-1096; MR42#1715.
[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.
[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.
[15]	J. Mitchem, An extension of Brooks' theorem to r-degenerate graphs, Discrete Math. 17 (1977) 291-298; MR 55#12561.
[16]	J. Mitchem, Maximal k-degenerate graphs, Utilitas Math. 11 (1977) 101-106.
[17]	G. Semanišin, On some variations of extremal graph problems, Discussiones Mathematicae Graph Theory 17 (1997) 67-76, doi: 10.7151/dmgt.1039.
[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]	J.M.S. Simoes-Pereira, A survey on k-degenerate graphs, Graph Theory Newsletter 5 (6) (75/76) 1-7; MR 55#199.