Trees with large neighborhood total domination number

Michael A. Henning, Kirsti Wash

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


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 languageEnglish
Pages (from-to)96-102
Number of pages7
JournalDiscrete Applied Mathematics
Publication statusPublished - 31 May 2015


  • Domination
  • Neighborhood total domination
  • Total domination

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Trees with large neighborhood total domination number'. Together they form a unique fingerprint.

Cite this