×

Tree domination in graphs. (English) Zbl 1112.05317

Summary: A subset \(S\) of \(V(G)\) is called a dominating set if every vertex in \(V(G)\setminus S\) is adjacent to some vertex in \(S\). The domination number \(\gamma(G)\) of \(G\) is the minimum cardinality taken over all dominating sets of \(G\). 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_{\text{tr}}(G)\) of \(G\) is the minimum cardinality taken over all minimal tree dominating sets of \(G\). In this paper, some exact values of the tree domination number and some properties of tree domination are presented. Best possible bounds for the tree domination number, and graphs achieving these bounds are given.
Relationships between the tree domination number and other domination invariants are explored, and some open problems are given.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite