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

Abstract

top
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.

How to cite

top

Mieczysł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. [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. [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. [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. [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. [5] G. Kalai, Weakly saturated graphs are rigid, Annals of Discrete Math. 20 (1984) 189-190. Zbl0576.05018
  6. [6] P. Turán, On the Theory of Graphs, Colloq. Math. 3 (1954) 19-30. Zbl0055.17004

NotesEmbed ?

top

You must be logged in to post comments.