Opuscula Math. 32, no. 1 (2012), 153-158
http://dx.doi.org/10.7494/OpMath.2012.32.1.153

Opuscula Mathematica

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

Marcin Krzywkowski

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.

Mathematics Subject Classification: 05C05, 05C69.

Full text (pdf)

• Marcin Krzywkowski
• Gdansk University of Technology, Faculty of Electronics, Telecommunications and Informatics, ul. Narutowicza 11/12, 80–233 Gdansk, Poland
• Revised: 2011-03-23.
• Accepted: 2011-03-28.