Neighborhood Total Domination and Maximum Degree in Triangle-Free Graphs

作者：Henning Michael A.^*; Mojdeh D. A.; Salehi M. R. Sayed

来源：Utilitas Mathematica, 2018, 107: 137-150.

• Domination
• Total domination
• Neighborhood total domination

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 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 showed that if G is a connected graph on it vertices with maximum degree Delta < n - 1, then gamma(nt)(G) <= n -Delta 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-6