Dominating set

Dominating set --- доминирующее множество.

A set [math]\displaystyle{ S \subseteq V }[/math] is a dominating set of [math]\displaystyle{ G }[/math] if for all [math]\displaystyle{ v \in V \setminus S }[/math] there is a vertex [math]\displaystyle{ u \in S }[/math] such that [math]\displaystyle{ (u,v) \in E(G) }[/math]. The minimum cardinality of a dominating set of [math]\displaystyle{ G }[/math] is called the domination number of [math]\displaystyle{ G }[/math]. It is well-known that determining the domination number of a graph is NPhard.

A dominating set [math]\displaystyle{ S }[/math] is called independent if the induced subgraph [math]\displaystyle{ \langle S \rangle }[/math] is empty; total if [math]\displaystyle{ \langle S \rangle }[/math] has no isolated vertex and connected if [math]\displaystyle{ \langle S \rangle }[/math] is connected. The minimum cardinality taken over all minimal independent (total/connected) dominating sets in [math]\displaystyle{ G }[/math] is called the independent (total/connected) domination number of [math]\displaystyle{ G }[/math] and is denoted by [math]\displaystyle{ \gamma_{i} }[/math] ([math]\displaystyle{ \gamma_{t} }[/math]/[math]\displaystyle{ \gamma_{c}$). For a vertex }[/math]v[math]\displaystyle{ of a graph }[/math]G = (V,E)[math]\displaystyle{ , the '''domination number }[/math]\gamma_{v(G)[math]\displaystyle{ of }[/math]G[math]\displaystyle{ relative to }[/math]v[math]\displaystyle{ } is the minimum cardinality of a dominating set in }[/math]G[math]\displaystyle{ that contains }[/math]v[math]\displaystyle{ . The '''average domination number''' of }[/math]G[math]\displaystyle{ is }[/math]\gamma_{av}(G) = \frac{1}{|V|}\sum_{v \in V} \gamma_{v}(G).[math]\displaystyle{ The '''independent domination number }[/math]i_{v(G)[math]\displaystyle{ of }[/math]G[math]\displaystyle{ relative to }[/math]v[math]\displaystyle{ } is the minimum cardinality of a maximal independent set in }[/math]G[math]\displaystyle{ that contains }[/math]v[math]\displaystyle{ . The '''average independent domination number''' of }[/math]G[math]\displaystyle{ is }[/math]i_{av}(G) = \frac{1}{|V|} \sum_{v \in V} i_{v}(G).[math]\displaystyle{ A '''dominating set of a digraph''' }[/math]\vec{G}$ is a set [math]\displaystyle{ S }[/math] of vertices such that for every vertex [math]\displaystyle{ v \not \in S }[/math] there exists some [math]\displaystyle{ u \in S }[/math] with [math]\displaystyle{ (u,v) \in E(\vec{G}) }[/math]. The domination number [math]\displaystyle{ \gamma(\vec{G}) }[/math] of [math]\displaystyle{ \vec{G} }[/math]} is defined as the cardinality of the smallest dominating set.

The dominating set problem is \emph{NP-complete on arbitrary graphs. It is also NPcomplete on several classes of graphs, including planar graphs, bipartite graphs and chordal graphs. The problem can be solved in polynomial time on, for example, AT-free graphs, pe\-rmuta\-tion graphs, interval graphs, and trees.

See also

• [math]\displaystyle{ k }[/math]-restricted total dominating number.