An upper bound on the total outer-independent domination number of a tree

Abstract

A total outer-independent dominating set of a graph \(G=(V(G),E(G))\) is a set \(D\) of vertices of \(G\) such that every vertex of \(G\) has a neighbor in \(D\), and the set \(V(G) \setminus D\) is independent. The total outer-independent domination number of a graph \(G\), denoted by \(\gamma_t^{oi}(G)\), is the minimum cardinality of a total outer-independent dominating set of \(G\). We prove that for every tree \(T\) of order \(n \geq 4\), with \(l\) leaves and \(s\) support vertices we have \(\gamma_t^{oi}(T) \leq (2n + s - l)/3\), and we characterize the trees attaining this upper bound.

Keywords

• total outer-independent domination
• total domination
• tree