Слабо алмазо-свободный граф

Материал из WikiGrapp
Версия от 16:01, 28 января 2010; Glk (обсуждение | вклад) (Создана новая страница размером '''Слабо алмазо-свободный граф''' (''Weakly diamond-free graph'') - Пусть вершина <math>V</math> та...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Слабо алмазо-свободный граф (Weakly diamond-free graph) - Пусть вершина [math]\displaystyle{ V }[/math] такова, что ее степень не превышает [math]\displaystyle{ 2\omega(G) - 1 }[/math], где [math]\displaystyle{ \omega(G) }[/math] --- плотность графа [math]\displaystyle{ G }[/math], и окрестность [math]\displaystyle{ N(v) }[/math] порождает алмазо-свободный подграф. Назовем ее WDF-вершиной. Граф называется WDF-графом, если каждый индуцированный подграф содержит WDF-вершину. Класс WDF-графов содержит хордальные и совершенные реберные графы.

Литература

[Discrete Math.]