PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2002 | 22 | 1 | 17-29
Tytuł artykułu

Weakly P-saturated graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Kategorie tematyczne
Wydawca
Rocznik
Tom
22
Numer
1
Strony
17-29
Opis fizyczny
Daty
wydano
2002
otrzymano
2000-08-20
poprawiono
2001-12-03
Twórcy
  • Institute of Mathematics, University of Zielona Góra, 65-246 Zielona Góra, Podgórna 50, Poland
  • Institute of Mathematics, University of Zielona Góra, 65-246 Zielona Góra, Podgórna 50, Poland
Bibliografia
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1155
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.