Distance domination-critical graphs Original Research Article

A set DD of vertices in a connected graph GG is called a kk-dominating set if every vertex in G−DG−D is within distance kk from some vertex of DD. The kk-domination number of GG, γk(G)γk(G), is the minimum cardinality over all kk-dominating sets of GG. A graph GG is kk-distance domination-critical if γk(G−x)<γk(G)γk(G−x)<γk(G) for any vertex xx in GG. This work considers properties of kk-distance domination-critical graphs and establishes a best possible upper bound on the diameter of a 2-distance domination-critical graph GG, that is, d(G)≤3(γ2−1)d(G)≤3(γ2−1) for γ2≥2γ2≥2.