## Abstract

In this paper, we continue the study of neighborhood total domination in graphs first studied by Arumugam and Sivagnanam (2011). A neighborhood total dominating set, abbreviated NTD-set, in a graph G is a dominating set S in G with the property that the subgraph induced by the open neighborhood of the set S has no isolated vertex. The neighborhood total domination number, denoted by ^{γnt}(G), is the minimum cardinality of a NTD-set of G. Every total dominating set is a NTD-set, implying that γ(G)≤^{γnt}(G)≤^{γt}(G), where γ(G) and ^{γt}(G) denote the domination and total domination numbers of G, respectively. Arumugam and Sivagnanam posed the problem of characterizing the connected graphs G of order n≥3 achieving the largest possible neighborhood total domination number, namely ^{γnt}(G)=⌈n/2⌉. A partial solution to this problem was presented by Henning and Rad (2013) who showed that 5-cycles and subdivided stars are the only such graphs achieving equality in the bound when n is odd. In this paper, we characterize the extremal trees achieving equality in the bound when n is even. As a consequence of this tree characterization, a characterization of the connected graphs achieving equality in the bound when n is even can be obtained noting that every spanning tree of such a graph belongs to our family of extremal trees.

Original language | English |
---|---|

Pages (from-to) | 96-102 |

Number of pages | 7 |

Journal | Discrete Applied Mathematics |

Volume | 187 |

DOIs | |

Publication status | Published - 31 May 2015 |

## Keywords

- Domination
- Neighborhood total domination
- Total domination

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics