For a hereditary property let denote the number of forbidden subgraphs contained in G. A graph G is said to be weakly -saturated, if G has the property and there is a sequence of edges of G̅, say , such that the chain of graphs has the following property: , 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 ₖ-saturated graphs of order n. We shall determine the number wsat(n,) for some hereditary properties.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1155,
author = {Mieczys\l aw Borowiecki and El\.zbieta Sidorowicz},
title = {Weakly P-saturated graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {22},
year = {2002},
pages = {17-29},
zbl = {1016.05044},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1155}
}
Mieczysław Borowiecki; Elżbieta Sidorowicz. Weakly P-saturated graphs. Discussiones Mathematicae Graph Theory, Tome 22 (2002) pp. 17-29. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1155/
[000] [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.
[001] [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. | Zbl 0126.39401
[002] [3] R. Lick and A. T. White, k-degenerated graphs, Canadian J. Math. 22 (1970) 1082-1096, doi: 10.4153/CJM-1970-125-1. | Zbl 0202.23502
[003] [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. | Zbl 0471.05038
[004] [5] G. Kalai, Weakly saturated graphs are rigid, Annals of Discrete Math. 20 (1984) 189-190. | Zbl 0576.05018
[005] [6] P. Turán, On the Theory of Graphs, Colloq. Math. 3 (1954) 19-30. | Zbl 0055.17004