Neighborhood total domination and maximum degree in triangle-free graphs - Henning, Michael A.; Mojdeh D.A.; Sayed Salehi M.R. (Utilitas Mathematica, 2018)
In this paper, we continue the study of neighborhood total domination in graphs first studied by Arumugam and Sivagnanam [Opuscula Math. 31 (2011), 519-531]. 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 5 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 showed that if G is a connected graph on n vertices with maximum degree < n - 1, then γnt(G) ≤ n - and pose the problem of determining the graphs G achieving equality in this bound. We provide a complete solution to this problem for triangle-free graphs. Further, we give a description involving the packing number of general graphs that achieve equality in the bound. © 2018 Utilitas Mathematica Publishing Inc. All rights reserved.