Changing and Unchanging Domination: A Classification
Document Type
Article
Publication Date
10-28-2003
Description
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.
Citation Information
Haynes, Teresa W.; and Henning, Michael A.. 2003. Changing and Unchanging Domination: A Classification. Discrete Mathematics. Vol.272(1). 65-79. https://doi.org/10.1016/S0012-365X(03)00185-7 ISSN: 0012-365X