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
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.
- Marcin Krzywkowski
- Gdansk University of Technology, Faculty of Electronics, Telecommunications and Informatics, ul. Narutowicza 11/12, 80–233 Gdansk, Poland
- Received: 2010-11-23.
- Revised: 2011-03-23.
- Accepted: 2011-03-28.
