- Tytuł:
- Gallais innequality for critical graphs of reducible hereditary properties
- Autorzy:
-
Mihók, Peter
Skrekovski, Riste - Powiązania:
- https://bibliotekanauki.pl/articles/743466.pdf
- Data publikacji:
- 2001
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
additive induced-hereditary property of graphs
reducible property of graphs
critical graph
Gallai's Theorem - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2001, 21, 2; 167-177
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł