Trees with large neighborhood total domination number

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 GG is a dominating set SS in GG with the property that the subgraph induced by the open neighborhood of the set SS has no isolated vertex. The neighborhood total domination number, denoted by γnt(G), is the minimum cardinality of a NTD-set of GG. Every total dominating set is a NTD-set, implying that γ(G)≤γnt(G)≤γt(G), where γ(G)γ(G) and γt(G)γt(G) denote the domination and total domination numbers of GG, respectively. Arumugam and Sivagnanam posed the problem of characterizing the connected graphs GG of order n≥3n≥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 nn is odd. In this paper, we characterize the extremal trees achieving equality in the bound when nn is even. As a consequence of this tree characterization, a characterization of the connected graphs achieving equality in the bound when nn is even can be obtained noting that every spanning tree of such a graph belongs to our family of extremal trees.