PDF

Discussiones Mathematicae Graph Theory 22(1) (2002) 17-29
DOI: https://doi.org/10.7151/dmgt.1155

Weakly P-Saturated Graphs

Mieczysław Borowiecki and Elżbieta Sidorowicz

Institute of Mathematics University of Zielona Góra
65-246 Zielona Góra, Podgórna 50, Poland
e-mail: M.Borowiecki@im.uz.zgora.pl
            E.Sidorowicz@im.uz.zgora.pl

Abstract

For a hereditary property P let k_P (G) denote the number of forbidden subgraphs contained in G. A graph G is said to be weakly P -saturated, if G has the property P and there is a sequence of edges of [`G], say e₁,e₂,…,e_l, such that the chain of graphs G = G₀ ⊂ G₀+e₁ ⊂ G₁+e₂ ⊂ … ⊂ G_l−1+e_l = G_l = K_n (G_i+1 = G_i+e_i+1) has the following property: k_P (G_i+1) > k_P(G_i), 0 ≤ i ≤ l−1.

In this paper we shall investigate some properties of weakly saturated graphs. We will find upper bound for the minimum number of edges of weakly D_k-saturated graphs of order n. We shall determine the number wsat(n,P) for some hereditary properties.

Keywords: graph, extremal problems, hereditary property, weakly saturated graphs.

2000 Mathematics Subject Classifications: 05C35.

References

[1]	B. Bollobás, Weakly k-saturated graphs, in: H. Sachs, H.-J. Voss and H. Walther, eds, Proc. Beiträge zur Graphentheorie, Manebach, 9-12 May, 1967 (Teubner Verlag, Leipzig, 1968) 25-31.
[2]	P. Erdős, A. Hajnal and J.W. Moon, A Problem in Graph Theory, Amer. Math. Monthly 71 (1964) 1107-1110, doi: 10.2307/2311408.
[3]	R. Lick and A. T. White, k-degenerated graphs, Canadian J. Math. 22 (1970) 1082-1096, doi: 10.4153/CJM-1970-125-1.
[4]	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.
[5]	G. Kalai, Weakly saturated graphs are rigid, Annals of Discrete Math. 20 (1984) 189-190.
[6]	P. Turán, On the Theory of Graphs, Colloq. Math. 3 (1954) 19-30.

Received 20 August 2000
Revised 3 December 2001