Weakly P-saturated graphs

• Autorzy: Mieczysław Borowiecki , Elżbieta Sidorowicz
• 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

graph; extremal problems; hereditary property; weakly saturated graphs

Kategorie tematyczne

• 05C35: Extremal problems

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2002
• Tom: 22
• Numer: 1
• Strony: 17-29

Daty

wydano

2002

otrzymano

2000-08-20

poprawiono

2001-12-03

Twórcy

autor

Mieczysław Borowiecki

• Institute of Mathematics, University of Zielona Góra, 65-246 Zielona Góra, Podgórna 50, Poland

autor

Elżbieta Sidorowicz

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

Identyfikatory

DOI

10.7151/dmgt.1155