DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 22(1) (2002) 17-29
DOI: 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 kP (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 e1,e2,…,el, such that the chain of graphs G = G0 ⊂ G0+e1 ⊂ G1+e2 ⊂ … ⊂ Gl−1+el = Gl = Kn (Gi+1 = Gi+ei+1) has the following property: kP (Gi+1) > kP(Gi), 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 Dk-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