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}/ }[/math]).

For a vertex [math]\displaystyle{ v }[/math] of a graph [math]\displaystyle{ G = (V,E) }[/math], the domination number [math]\displaystyle{ \gamma_{v}(G) }[/math] of [math]\displaystyle{ G }[/math] relative to [math]\displaystyle{ v }[/math] is the minimum cardinality of a dominating set in [math]\displaystyle{ G }[/math] that contains [math]\displaystyle{ v }[/math]. The average domination number of [math]\displaystyle{ G }[/math] is

[math]\displaystyle{ \gamma_{av}(G) = \frac{1}{|V|}\sum_{v \in V} \gamma_{v}(G). }[/math]

The independent domination number [math]\displaystyle{ i_{v}(G) }[/math] of [math]\displaystyle{ G }[/math] relative to [math]\displaystyle{ v }[/math] is the minimum cardinality of a maximal independent set in [math]\displaystyle{ G }[/math] that contains [math]\displaystyle{ v }[/math]. The average independent domination number of [math]\displaystyle{ G }[/math] is

[math]\displaystyle{ i_{av}(G) = \frac{1}{|V|} \sum_{v \in V} i_{v}(G). }[/math]

A dominating set of a digraph [math]\displaystyle{ \vec{G} }[/math] 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 NP-complete on arbitrary graphs. It is also NP-complete 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, permutation graphs, interval graphs, and trees.

See also

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