A Generalization of Domination Critical Graphs
Document Type
Article
Publication Date
11-1-2000
Description
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 K3 o K1.
Citation Information
Phillips, James B.; Haynes, Teresa W.; and Slater, Peter J.. 2000. A Generalization of Domination Critical Graphs. Utilitas Mathematica. Vol.58 129-144. ISSN: 0315-3681