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 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 gamma(nt) (G), is the minimum cardinality of a NTD-set of G. Every total dominating set is a NTD-set, implying that gamma(G) <= gamma(nt)(G) <= gamma(t) (G), where gamma(G) and gamma(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 gamma(nt)(G) = inverted right perpendicularn/2inverted right perpendicular. 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. (C) 2015 Elsevier B.V. All rights reserved.