Distance domination-critical graphs

A set D of vertices in a connected graph G is called a k-dominating set if every vertex in G - D is within distance k from some vertex of D. The k-domination number of G, gamma(k)(G), is the minimum cardinality over all k-dominating sets of G. A graph G is k-distance domination-critical if gamma(k)(G - x) < gamma(k)(G) for any vertex x in G. This work considers properties of k-distance domination-critical graphs and establishes a best possible upper bound on the diameter of a 2-distance domination-critical graph G, that is, d(G) <= 3(gamma(2) - 1) for gamma(2) >= 2. (C) 2007 Elsevier Ltd. All rights reserved.