Dominating function

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.