Gamma t(G)-Excellent graph

Материал из WikiGrapp
Перейти к навигации Перейти к поиску

[math]\displaystyle{ \gamma_{t}(G) }[/math]-Excellent graph --- [math]\displaystyle{ \gamma_{t}(G) }[/math]-превосходный граф.

A graph [math]\displaystyle{ G }[/math] is called [math]\displaystyle{ \gamma_{t}(G) }[/math]-excellent graph if every vertex of [math]\displaystyle{ G }[/math] belongs to some total dominating set of mini\-mal cardinality. A family of [math]\displaystyle{ \gamma_{t}(G) }[/math]-excellent trees (trees where every vertex is in some mini\-mum dominating set) is properly contained in the set of [math]\displaystyle{ i }[/math]-excellent trees (trees where every vertex is in some minimum independent dominating set).

In general, for a graph [math]\displaystyle{ G }[/math], let [math]\displaystyle{ {\mathcal P} }[/math] denote a property of sets [math]\displaystyle{ S \subseteq V }[/math] of vertices. We call a set [math]\displaystyle{ S }[/math] with the property [math]\displaystyle{ {\mathcal P} }[/math] having [math]\displaystyle{ \{ }[/math] minimum, maximum [math]\displaystyle{ \} }[/math]

cardinality [math]\displaystyle{ \mu(G) }[/math] a [math]\displaystyle{ \mu(G) }[/math]-set. A vertex is called [math]\displaystyle{ \mu }[/math]-good if it is contained in some [math]\displaystyle{ \mu(G) }[/math]-set and [math]\displaystyle{ \mu }[/math]-bad otherwise. A graph [math]\displaystyle{ G }[/math] is called [math]\displaystyle{ \mu }[/math]-excellent if every vertex in [math]\displaystyle{ V }[/math] is [math]\displaystyle{ \mu }[/math]-good.