K-Насыщенный граф

Материал из WikiGrapp
Версия от 14:59, 24 ноября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''<math>k</math>-Насыщенный граф''' (''<math>k</math>-Saturated graph'') - граф, который не содержит ...)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

k-Насыщенный граф (k-Saturated graph) - граф, который не содержит полный граф K_{k} k \geq 3, но добавление любого ребра приводит к возникновению K_{k}. Известно, что если G k-насыщенный на n \geq k-2 вершинах, то |E(G)| \geq
(k-2)n - \left(\begin{array}{c} k-1 \\ 2 \end{array} \right ).

Литература

[J. Graph Theory]