PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo

## Discussiones Mathematicae Graph Theory

2002 | 22 | 1 | 17-29
Tytuł artykułu

### Weakly P-saturated graphs

Autorzy
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.
Słowa kluczowe
EN
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
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
autor
• 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