Total domination stability in graphs

Michael A. Henning, Marcin Krzywkowski

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

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 languageEnglish
Pages (from-to)246-255
Number of pages10
JournalDiscrete Applied Mathematics
Volume236
DOIs
Publication statusPublished - 19 Feb 2018

Keywords

  • Total domination
  • Total domination stability

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Total domination stability in graphs'. Together they form a unique fingerprint.

Cite this