Neighborhood total domination and maximum degree in triangle-free graphs

Michael A. Henning, D. A. Mojdeh, M. R. Sayed Salehi

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)137-150
Number of pages14
JournalUtilitas Mathematica
Publication statusPublished - Jun 2018


  • Domination
  • Neighborhood total domination
  • Total domination

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Applied Mathematics


Dive into the research topics of 'Neighborhood total domination and maximum degree in triangle-free graphs'. Together they form a unique fingerprint.

Cite this