Irredundance perfect graph: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Новая страница: «'''Irredundance perfect graph''' --- неизбыточно совершенный граф. A graph <math>G</math> is an '''irredundance perfect graph''', if for …»)
 
Нет описания правки
 
Строка 8: Строка 8:


A graph <math>G</math> is '''minimal irredundance imperfect''' if <math>G</math> is not
A graph <math>G</math> is '''minimal irredundance imperfect''' if <math>G</math> is not
irredun\-dan\-ce perfect and <math>ir(H) = \gamma(H)</math> for every proper
irredundance perfect and <math>ir(H) = \gamma(H)</math> for every proper
induced subgraph <math>H</math> of <math>G</math>.
induced subgraph <math>H</math> of <math>G</math>.



Текущая версия от 14:41, 24 мая 2011

Irredundance perfect graph --- неизбыточно совершенный граф.

A graph [math]\displaystyle{ G }[/math] is an irredundance perfect graph, if for every induced subgraph [math]\displaystyle{ H }[/math] of [math]\displaystyle{ G }[/math] holds the equality [math]\displaystyle{ ir(H) = \gamma(H) }[/math], where [math]\displaystyle{ ir(H) }[/math] is the irredundance number and [math]\displaystyle{ \gamma(H) }[/math] is the domination number. A graph [math]\displaystyle{ G }[/math] is called [math]\displaystyle{ k }[/math]-irredundance perfect ([math]\displaystyle{ k \geq 1 }[/math]) if [math]\displaystyle{ ir(H) = \gamma(H) }[/math] for every induced subgraph [math]\displaystyle{ H }[/math] of [math]\displaystyle{ G }[/math] with [math]\displaystyle{ ir(H) \leq k }[/math].

A graph [math]\displaystyle{ G }[/math] is minimal irredundance imperfect if [math]\displaystyle{ G }[/math] is not irredundance perfect and [math]\displaystyle{ ir(H) = \gamma(H) }[/math] for every proper induced subgraph [math]\displaystyle{ H }[/math] of [math]\displaystyle{ G }[/math].

The first sufficient condition, for a graph to be irredundance perfect, in terms of a family of forbidden induced subgraphs is due to Bollob\'{a}s and Cockayne (1979).