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.