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

Материал из WEGA
Версия от 11:06, 9 сентября 2011; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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