Signed total domination

Signed total domination --- знаковое тотальное доминирование.

A function [math]\displaystyle{ f: \; V(G) \rightarrow \{-1,1\} }[/math] defined on the vertices of a graph [math]\displaystyle{ G }[/math] is a signed total domination funciton (STDF), if the sum of its values over any open neighborhood is at least 1. An STDF [math]\displaystyle{ f }[/math] is minimal, if there does not exist an STDF [math]\displaystyle{ g: \; V(G) \rightarrow \{-1,1\} }[/math], [math]\displaystyle{ f \neq g }[/math], for which [math]\displaystyle{ g(v) \leq f(v) }[/math] for every [math]\displaystyle{ v \in V(G) }[/math]. The weight of an STDF is the sum of its values over all vertices. The signed total domination number of [math]\displaystyle{ G }[/math] is the minimum weight of an STDF of [math]\displaystyle{ G }[/math], while the upper signed total domination number of [math]\displaystyle{ G }[/math] is the maximum weight of a minimal STDF on [math]\displaystyle{ G }[/math].