Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Gallai's Theorem

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Gallai's innequality for critical graphs of reducible hereditary properties

100%

Mihók P., Skrekovski R.

Discussiones Mathematicae Graph Theory

2001

tom 21

nr 2

167-177

In this paper Gallai's inequality on the number of edges in critical graphs is generalized for reducible additive induced-hereditary properties of graphs in the following way. Let $𝓟₁,𝓟₂,...,𝓟ₖ$ (k ≥ 2) be additive induced-hereditary properties, $𝓡 = 𝓟₁ ∘ 𝓟₂ ∘ ... ∘𝓟ₖ$ and $δ = ∑_{i=1}^k δ(𝓟_i)$. Suppose that G is an 𝓡 -critical graph with n vertices and m edges. Then 2m ≥ δn + (δ-2)/(δ²+2δ-2)*n + (2δ)/(δ²+2δ-2) unless 𝓡 = 𝓞² or $G = K_{δ+1}$. The generalization of Gallai's inequality for 𝓟-choice critical graphs is also presented.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Mihók P.

1 Skrekovski R.

1 2001

Wyniki wyszukiwania

Gallai's innequality for critical graphs of reducible hereditary properties