Слабо алмазо-свободный граф: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Слабо алмазо-свободный граф''' (''Weakly diamond-free graph'') - Пусть вершина <math>V</math> та...)
(нет различий)

Версия от 16:01, 28 января 2010

Слабо алмазо-свободный граф (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.]