Tree Domination in Graphs

Abstract

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