A generalization of domination critical graphs

Abstract

A graph G is called domination critical if the removal of any vertex from G causes the domination number of the resulting graph to be reduced by one. Generalizing this concept, we define a graph G with domination number γ(G) to be (γ, t)-critical if the removal of any t vertices from a packing reduces the domination number by exactly t. Given any positive integers j and t, where t ≤ j, we show that there exists a (j, t)-critical graph. We also characterize the (γ, γ)-critical and the (γ, γ - 1)-critical graphs. Finally, we show that no tree is (γ, t)-critical and that the only unicyclic (γ, t)-critical graphs are the domination critical cycles and the corona K₃ o K₁.