Domination parameters and edge-removal-critical graphs Original Research Article

For π any of the basic domination parameters ir, γ, i, β, Γ or IR, we study graphs for which π increases whenever an edge is removed (π-ER-critical graphs) and graphs for which π decreases whenever an edge is removed (π−-ER-critical graphs). The latter case is only possible if π=i or (perhaps) π=ir. We give examples of classes of π-ER-critical graphs for π an upper domination parameter and characterize these graphs in terms of the existence of π-sets with certain properties. We prove necessary conditions for a graph to be ir-ER-critical but not γ-ER-critical and use these to characterize ir-ER-critical graphs with ir=2. Finally, we exhibit classes of graphs that are i−-ER-critical.