Changing and unchanging domination: A classification

Teresa W. Haynes, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

23 Citations (Scopus)


The six classes of graphs resulting from the changing or unchanging of the domination number of a graph when a vertex is deleted, or an edge is deleted or added are considered. Each of these classes has been studied individually in the literature. We consider relationships among the classes, which are illustrated in a Venn diagram. We show that no subset of the Venn diagram is empty for arbitrary graphs, and prove that some of the subsets are empty for connected graphs. Our main result is a characterization of trees in each subset of the Venn diagram.

Original languageEnglish
Pages (from-to)65-79
Number of pages15
JournalDiscrete Mathematics
Issue number1
Publication statusPublished - 28 Oct 2003
Externally publishedYes


  • Changing and unchanging domination numbers
  • Critical domination
  • Domination

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Changing and unchanging domination: A classification'. Together they form a unique fingerprint.

Cite this