Domination parameters and added matchings

Wayne Goddard, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)2009-2024
Number of pages16
JournalAequationes Mathematicae
Volume99
Issue number4
DOIs
Publication statusPublished - Aug 2025

ASJC Scopus subject areas

  • General Mathematics
  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Domination parameters and added matchings'. Together they form a unique fingerprint.

Cite this