# Weakly P-saturated graphs

Mieczysław Borowiecki; Elżbieta Sidorowicz

Discussiones Mathematicae Graph Theory (2002)

- Volume: 22, Issue: 1, page 17-29
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMieczysław Borowiecki, and Elżbieta Sidorowicz. "Weakly P-saturated graphs." Discussiones Mathematicae Graph Theory 22.1 (2002): 17-29. <http://eudml.org/doc/270559>.

@article{MieczysławBorowiecki2002,

abstract = {For a hereditary property let $k_\{\}(G)$ 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 $e₁,e₂,...,e_l$, such that the chain of graphs $G = G₀ ⊂ G_0 + 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_\{\}(G_\{i+1\}) > k_\{\}(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 ₖ-saturated graphs of order n. We shall determine the number wsat(n,) for some hereditary properties.},

author = {Mieczysław Borowiecki, Elżbieta Sidorowicz},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {graph; extremal problems; hereditary property; weakly saturated graphs},

language = {eng},

number = {1},

pages = {17-29},

title = {Weakly P-saturated graphs},

url = {http://eudml.org/doc/270559},

volume = {22},

year = {2002},

}

TY - JOUR

AU - Mieczysław Borowiecki

AU - Elżbieta Sidorowicz

TI - Weakly P-saturated graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2002

VL - 22

IS - 1

SP - 17

EP - 29

AB - For a hereditary property let $k_{}(G)$ 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 $e₁,e₂,...,e_l$, such that the chain of graphs $G = G₀ ⊂ G_0 + 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_{}(G_{i+1}) > k_{}(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 ₖ-saturated graphs of order n. We shall determine the number wsat(n,) for some hereditary properties.

LA - eng

KW - graph; extremal problems; hereditary property; weakly saturated graphs

UR - http://eudml.org/doc/270559

ER -

## References

top- [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. Zbl0126.39401
- [3] R. Lick and A. T. White, k-degenerated graphs, Canadian J. Math. 22 (1970) 1082-1096, doi: 10.4153/CJM-1970-125-1. Zbl0202.23502
- [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. Zbl0471.05038
- [5] G. Kalai, Weakly saturated graphs are rigid, Annals of Discrete Math. 20 (1984) 189-190. Zbl0576.05018
- [6] P. Turán, On the Theory of Graphs, Colloq. Math. 3 (1954) 19-30. Zbl0055.17004

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.