Tree dominating set

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

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.