Dominating function: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Dominating function''' --- доминирующая функция. A '''signed dominating function''' of <math>G</math> is defined as <math>g: \; V \rightarrow…») |
(нет различий)
|
Текущая версия от 14:51, 5 апреля 2011
Dominating function --- доминирующая функция.
A signed dominating function of [math]\displaystyle{ G }[/math] is defined as [math]\displaystyle{ g: \; V \rightarrow \{\pm1\} }[/math] satisfying [math]\displaystyle{ g(N[v]) \geq 1 }[/math] for all [math]\displaystyle{ v \in V }[/math]. A signed dominating function [math]\displaystyle{ g }[/math] is minimal if there does not exist a signed dominating function [math]\displaystyle{ h \neq g }[/math] satisfying [math]\displaystyle{ h(v) \geq g(v) }[/math] for every [math]\displaystyle{ v \in V }[/math]. The signed domination number of a graph [math]\displaystyle{ G }[/math] is defined as [math]\displaystyle{ \gamma_{s}(G) = \min\{g(V)| \;g }[/math] is a minimal signed dominating function of [math]\displaystyle{ G\} }[/math].
A minus dominating function is defined as a function [math]\displaystyle{ g: \; V \rightarrow \{0,\pm1\} }[/math] such that [math]\displaystyle{ g(N[v]) \geq 1 }[/math] for all [math]\displaystyle{ v \in V }[/math]. Similarly, we can define a minimal minus dominating function, the minus domination number [math]\displaystyle{ \gamma^{-}(G) }[/math] of [math]\displaystyle{ G }[/math].
A majority dominating function of a graph [math]\displaystyle{ G }[/math] is defined as a funmction [math]\displaystyle{ g: \; V \rightarrow \{\pm1\} }[/math] such that for at least half the vertices [math]\displaystyle{ v \in V }[/math], [math]\displaystyle{ g(N[v]) \geq 1 }[/math]. Similarly, a minimal majority dominating function and the majority domination number [math]\displaystyle{ \gamma_{maj}(G) }[/math] of [math]\displaystyle{ G }[/math] are defined.