## Abstract

A set D of vertices in an isolate-free graph G is a total dominating set of G if every vertex is adjacent to a vertex in D. The total domination number, γ_{t}(G), of G is the minimum cardinality of a total dominating set of G. We note that γ_{t}(G)≥2 for every isolate-free graph G. A non-isolating set of vertices in G is a set of vertices whose removal from G produces an isolate-free graph. The γ_{t}^{−}-stability, denoted st_{γt}^{−}(G), of G is the minimum size of a non-isolating set S of vertices in G whose removal decreases the total domination number. We show that if G is a connected graph with maximum degree Δ satisfying γ_{t}(G)≥3, then st_{γt}^{−}(G)≤2Δ−1, and we characterize the infinite family of trees that achieve equality in this upper bound. The total domination stability, st_{γt}(G), of G is the minimum size of a non-isolating set of vertices in G whose removal changes the total domination number. We prove that if G is a connected graph with maximum degree Δ satisfying γ_{t}(G)≥3, then st_{γt}(G)≤2Δ−1.

Original language | English |
---|---|

Pages (from-to) | 246-255 |

Number of pages | 10 |

Journal | Discrete Applied Mathematics |

Volume | 236 |

DOIs | |

Publication status | Published - 19 Feb 2018 |

## Keywords

- Total domination
- Total domination stability

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics