Tree dominating set

Материал из WikiGrapp
Версия от 17:23, 16 августа 2011; Glk (обсуждение | вклад) (Новая страница: «'''Tree dominating set''' --- древесное доминирующее множество. A '' dominating set'' <math>S</math> is called a ''' connected (acycli…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

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.