Abstract
We consider the augmentation problem of how domination parameters behave when a perfect matching P of the complement is added to the graph. We focus on the case that the graph is a tree, and inter alia show that if T is a tree of even order n that is not a star, then T+P has domination number at most 2n/5, independent domination number at most n/2-1, and total domination and upper domination number at most n/2. Further, there exists a choice of P such that T+P has total domination number at most n/3. All these bounds are sharp.
| Original language | English |
|---|---|
| Pages (from-to) | 2009-2024 |
| Number of pages | 16 |
| Journal | Aequationes Mathematicae |
| Volume | 99 |
| Issue number | 4 |
| DOIs | |
| Publication status | Published - Aug 2025 |
ASJC Scopus subject areas
- General Mathematics
- Discrete Mathematics and Combinatorics
- Applied Mathematics