# Tree dominating set

Перейти к:навигация, поиск

Tree dominating set --- древесное доминирующее множество. A dominating set $S$ is called a connected (acyclic) dominating set if the induced subgraph $\langle S \rangle$ is connected (acyclic). The connected (acyclic) domination number is the minimum cardinality taken over all minimal connected (acyclic) dominating sets of $G$.

If $\langle S \rangle$ is both connected and acyclic, then $\langle S \rangle$ is a tree. A dominating set $S$ is called a tree dominating set, if the induced subgraph $\langle S \rangle$ is a tree. The tree domination number $\gamma_{tr}(G)$ of $G$ is the minimum cardinality taken over all minimal tree dominating sets of $G$.