Vertex domination‐critical graphs

Abstract

Abstract A graph G is vertex domination‐critical if for any vertex v of G the domination number of G ‐ v is less than the domination number of G . If such a graph G has domination number γ, it is called γ‐critical. Brigham et al. studied γ‐critical graphs and posed the following questions: (1) If G is a γ‐critical graph, is | V | ≥ (δ + 1)(γ ‐ 1) + 1?(2) If a γ‐critical graph G has (Δ + 1)(γ ‐ 1) + 1 vertices, is G regular? (3) Does i = γ for all γ‐critical graphs? (4) Let d be the diameter of the γ‐critical graph G . Does d ≤ 2(γ ‐ 1) always hold? We show that the first and third questions have a negative answer and the others have a positive answer.