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

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

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

Литература

[J. Graph Theory]