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.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.